/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						     adventure_ai.h

	$Header: /heroes4/adventure_ai.h $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "adventure_ai.h"

#include "adv_dwelling.h"
#include "adv_shipyard.h"
#include "adventure_frame.h"
#include "adventure_map.h"
#include "adventure_map_window.h"
#include "adventure_object.h"
#include "adventure_path.h"
#include "ai_army_data_cache.h"
#include "ai_importance.h"
#include "ai_town_data_cache.h"
#include "ai_value.h"
#include "alignment_relationship.h"
#include "army.h"
#include "army_array.h"
#include "army_mover.h"
#include "basic_dialog.h"
#include "bound_handler.h"
#include "building_traits.h"
#include "caravan.h"
#include "creature.h"
#include "creature_traits.h"
#include "direction.h"
#include "enum_operations.h"
#include "external_string.h"
#include "footprint.h"
#include "game_application.h"
#include "hero_class_properties.h"
#include "options.h"
#include "ownable_garrisonable_adv_object.h"
#include "pathfinding_subject.h"
#include "pathfinding_subject_ptr.h"
#include "platform.h"
#include "player.h"
#include "player_list.h"
#include "progress_bar.h"
#include "progress_handler.h"
#include "random.h"
#include "replace_keywords.h"
#include "simple_dialog.h"
#include "simulated_combat.h"
#include "spell_properties.h"
#include "terrain.h"
#include "town.h"
#include "town_list.h"

#include "profile.h"

const float	k_value_half_army_death = k_value_army_death / 2;
const int	k_ai_danger_movement_buffer = 400;
const int	k_ai_max_turns_of_move_eval = 5;
const float	k_ai_move_value_multiplier = 100.0f;
const float	k_ai_high_exploration_value = 10000.0f;
const float	k_ai_low_exploration_value = 0.5f;
const float	k_ai_danger_escape_value = 1.0f;
const int	k_ai_value_search_distance = std::numeric_limits< int >::max();
const float	k_ai_value_of_continuation = 1000.0f;
const float	k_ai_value_bonus_for_buying_hero = 2000.0f;
const float k_ai_simulation_attacker_effectiveness = 0.85f;
const float k_ai_simulation_defender_effectiveness = 1.15f;

double const k_half_pi = k_pi / 2;
double const k_quarter_pi = k_pi / 4;
double const k_three_quarter_pi = k_pi * 0.75f;
double const k_double_pi = k_pi * 2;
double const k_under_half_pi = k_pi * 0.49f; // slightly smaller to allow imperfection in range comparisons.

double const k_directions[] =
{
	k_pi,
	k_three_quarter_pi,
	k_half_pi,
	k_quarter_pi,
	0,
	-k_quarter_pi,
	-k_half_pi,
	-k_three_quarter_pi,
	-k_pi
};

typedef t_ownable_garrisonable_adv_object_list t_garrison_list;

namespace {
	void set_ai_effectiveness( t_simulated_combat& simulation, t_creature_array* attacker, t_creature_array* defender )
	{
		t_player*			attacking_player = attacker->get_owner();
		t_player*			defending_player = defender->get_owner();
		bool				attacker_is_human = attacking_player && !attacking_player->is_computer() && !attacking_player->is_eliminated();
		bool				defender_is_human = defending_player && !defending_player->is_computer() && !defending_player->is_eliminated();
		t_adventure_map&	adventure_map = *attacker->get_map();

		if (!attacker_is_human && !defender_is_human 
				&& 
					( ((attacking_player == NULL) && ( defending_player != NULL))
						||
						((attacking_player != NULL) && (defending_player == NULL)) ) )
		{
			t_difficulty difficulty = adventure_map.get_player_difficulty(); 
			float effectiveness = 0.0f;
			switch (difficulty)
			{
				case k_difficulty_easy:
					effectiveness = 1.0f;
					break;
				case k_difficulty_normal:
					effectiveness = 1.30f;
					break;
				case k_difficulty_hard:
					effectiveness = 1.37f;
					break;
				case k_difficulty_expert:
					effectiveness = 1.44f;
					break;
				case k_difficulty_impossible:
					effectiveness = 1.50f;
					break;
			}
			if (attacking_player == NULL)
			{
				simulation.set_effectiveness( false, 1.0f );
				simulation.set_effectiveness( true, effectiveness );
			}
			else
			{
				simulation.set_effectiveness( true, 1.0f );
				simulation.set_effectiveness( false, effectiveness );
			}
		}
		else
		{
			simulation.set_effectiveness( false, k_ai_simulation_attacker_effectiveness );
			simulation.set_effectiveness( true, k_ai_simulation_defender_effectiveness );
		}
	}

	bool is_fixed_army( t_creature_array const& army )
	{
		return (army.get_patrol_radius() != -1) || (army.get_importance() != k_ai_importance_normal);
	}

	void apply_locks( t_creature_array const& target, t_ai_army_builder::t_locked_creatures& army_locks )
	{
		for (int i = 0; i < t_creature_array::k_size; i++)
		{
			if (target[i].get_number() != 0)
				army_locks.set(i, true);
		}
	}

	void build_artifact_list( t_creature_stack& creature, t_artifact_list& artifacts )
	{
		int size = creature.get_backpack_count();
		for (int i = size - 1; i >= 0; --i)
		{
			artifacts.push_back( creature.get_backpack_slot(i) );
			creature.remove_backpack(i);
		}

		t_hero* hero = creature.get_hero();
		if (hero == NULL) 
			return;

		for (t_artifact_slot slot = t_artifact_slot(0); slot < k_artifact_slot_hero_count; enum_incr(slot))
		{
			t_artifact const& artifact = hero->get_artifact( slot );
			if (artifact.get_icon() != k_artifact_none)
			{
				artifacts.push_back( artifact );
				hero->remove( slot );
			}
		}
	}

	bool should_neutral_army_attack( t_creature_array const& attacker, t_creature_array const& defender )
	{
		float our_value = attacker.ai_value();
		return (our_value + our_value) > defender.ai_value();
	}

	t_external_string const k_text_next_player( "next_player.misc" );

	int offset_to_direction( int col_distance, int row_distance, double& radian_direction )
	{
		radian_direction = atan2((double)col_distance, (double)row_distance);

		double target_heading = ((radian_direction + k_pi) / k_double_pi) * 8;
		double floored_direction;
		double remainder = modf( target_heading, &floored_direction);
		int integer_direction = floored_direction;
		if (remainder > 0.50f) integer_direction++;

		integer_direction = 8 - integer_direction;
		if (integer_direction == 8) 
			integer_direction = 0;

		return integer_direction;
	}

	inline t_creature_array* determine_best_army( t_creature_array& army, t_creature_array* best_army, float& best_army_value, bool& last_army )
	{
		if ( (army.get_movement() > 0) && !army.get_ai_data_cache()->is_sleeping() )
		{
			if (best_army != NULL)
				last_army = false;
			float army_value = army.ai_value();
			// The best army is the weakest (from the point of view of movement order selection.)
			if ((army_value < best_army_value) || (best_army == NULL)) 
			{
				best_army_value = army_value;
				best_army = &army;
			}
		}
		return best_army;
	}

	class t_compare_creature_value
	{
	public:
		t_compare_creature_value( t_adventure_ai const& ai ) : m_ai(ai) {}

		bool operator()( t_creature_stack_ptr const& left, 
		                 t_creature_stack_ptr const& right ) const
		{
			return 
					m_ai.get_cache().get_ai_value(left) >
					m_ai.get_cache().get_ai_value(right);
		}
	protected:
		t_adventure_ai const& m_ai;
	};

	class t_compare_town_value
	{
	public:
		t_compare_town_value( t_adventure_ai const& ai ) : m_ai(ai) {}

		bool operator()( t_town_ptr const& left, 
		                 t_town_ptr const& right ) const
		{
			return 
					m_ai.get_cache().get_ai_value(left) >
					m_ai.get_cache().get_ai_value(right);
		}
	protected:
		t_adventure_ai const& m_ai;
	};

	int count_heroes(t_creature_array const* array) 
	{
		int count = 0;
		for (int i = 0; i < t_creature_array::k_size; i++)
		{
			t_hero const* hero = (*array)[i].get_const_hero();
			if (hero != NULL) count++;
		}
		return count;
	}

	bool get_adjacent_space( t_adventure_map& map, t_adventure_object const* object, t_adv_map_point& point )
	{
		if (!object->get_trigger_cell( point ))
			return false;
	
		bool trigger_is_land = map.is_land( point );

		for (t_direction direction = t_direction(0); direction < k_direction_count; enum_incr(direction))
		{
			t_adv_map_point seed_point = point + get_direction_offset( direction );
			if ( map.is_valid( seed_point ) 
					&& ( map.is_land( seed_point ) == trigger_is_land ) 
					&& ( (map.get_trigger_object( seed_point, t_direction( (direction + 4) & 7 ), 0 ) != NULL) ))
			{
				point = seed_point;
				return true;
			}
		}
		return false;
	}

	bool is_expendable_object( t_adventure_object const* object )
	{
		t_stationary_adventure_object const* stationary_object = dynamic_cast<t_stationary_adventure_object const*>(object);
		if (stationary_object == NULL)
			return false;

		t_adv_object_type types[] =
		{
			k_adv_object_artifact,
			k_adv_object_campfire,
			k_adv_object_corpse,
			k_adv_object_flotsam,
			k_adv_object_keymaster_tent,
			k_adv_object_lighthouse,
			k_adv_object_material_pile,
			k_adv_object_obelisk,
			k_adv_object_treasure
		};

		int size = sizeof(types) / sizeof(t_adv_object_type);
		return std::find(&types[0], &types[size], stationary_object->get_type().get()) != &types[size];
	}	
}

void request_player( t_adventure_map& map, t_player const* player )
{
	assert(player);
	if (map.is_hotseat() && !player->is_computer())
	{
		int player_number = map.get_player_number( player->get_color() );
		if (player_number == map.get_player_number())
			return;

		assert( map.get_map_window() != 0 && map.get_map_window()->get_frame() != 0 );
		t_adventure_frame * frame = map.get_map_window()->get_frame();
		t_player_info_hider player_info_hider( *frame );

		// Temporarily set the team view to 'k_player_gray'.  This will shroud everything.
		frame->set_team_view( k_player_gray );

		ok_dialog( replace_keywords( k_text_next_player, "%player_name",
									 player->get_name() ), true );

		map.set_player( player_number );
		frame->update();
	} 
}


std::auto_ptr< t_creature_array > ai_deep_copy_of_creature_array_minus_hero( t_creature_array const& army );

class t_value_pathfinding_subject : public t_creature_array
{
public:
	t_value_pathfinding_subject( t_adventure_map * map, t_adventure_object const* object, int owner_number );

	// Overrides for creature array
	virtual t_adventure_map*	get_map() const;
	virtual int					get_movement( bool sea_move ) const;
	virtual int					get_max_movement( bool sea_move ) const;
	virtual int					get_owner_number() const;
	virtual t_adv_map_point		get_position() const;

private:
	t_adventure_map*			m_map;
	t_adventure_object const*	m_object;
	int							m_owner_number;
};

t_value_pathfinding_subject::t_value_pathfinding_subject( t_adventure_map * map, t_adventure_object const* object, int owner_number )
	: m_map( map ), m_object( object ), m_owner_number(owner_number)
{
}

t_adventure_map* t_value_pathfinding_subject::get_map() const
{
	return m_map;
}

int t_value_pathfinding_subject::get_movement( bool sea_move ) const
{
	return k_ai_value_search_distance;
}

int t_value_pathfinding_subject::get_max_movement( bool sea_move ) const
{
	return k_ai_value_search_distance;
}

int	t_value_pathfinding_subject::get_owner_number() const
{
	return m_owner_number;
}

t_adv_map_point t_value_pathfinding_subject::get_position() const
{
	return m_object->get_position();
}

class t_ai_army_mover : public t_army_mover
{
public:
	t_ai_army_mover( t_adventure_map_window* window, t_army* army, t_adventure_ai* ai, 
						t_adventure_path_finder const* path_finder, bool alternate_dest_search = true );

protected:
	bool				m_alt_dest_search;
	t_adventure_ai*		m_ai;

	virtual void on_starting_new_square();
};

t_ai_army_mover::t_ai_army_mover( t_adventure_map_window* window, 
									t_army* army, 
									t_adventure_ai* ai,
									t_adventure_path_finder const* path_finder,
									bool alternate_dest_search )
	:	t_army_mover( window, army, true, path_finder ), 
		m_alt_dest_search(alternate_dest_search),
		m_ai(ai)
{
}

void t_ai_army_mover::on_starting_new_square()
{
	declare_timer( timer, "t_ai_army_mover::on_starting_new_square()" );
	if (m_alt_dest_search)
	{
		if (m_ai->consider_alternate_destinations(true))
			end_move();
	}
}

class t_ai_progress_bar : public t_basic_dialog
{
public:
	t_ai_progress_bar( t_window* parent, const char * bar_layer, const char * label );

	t_progress_handler* get_handler();
protected:
	t_progress_bar* m_bar;
};

t_ai_progress_bar::t_ai_progress_bar( t_window* parent, const char * bar_layer, const char * label )
                     : t_basic_dialog( parent )
{
	m_bar = new t_progress_bar( t_screen_point(0,0), this, bar_layer );
	add_display_window( m_bar, label );

	t_screen_rect  rect = get_parent()->get_client_rect();
	t_screen_point point( rect.width(), rect.height() );

	open( point, rect, true, k_align_center, false );
	point.x = ((rect.width() - get_width()) / 2);
	point.y = rect.height() - get_height();
	move( point );
}

t_progress_handler* t_ai_progress_bar::get_handler()
{
	return m_bar;
}


int get_map_index( t_adventure_map& map, t_adv_map_point const& point )
{
	return 
		( (point.on_bridge * map.get_num_levels() + point.level) * map.get_size() + point.row )
			* map.get_size() + point.column;
}

t_ai_army::t_ai_army( t_adventure_map* map, t_player* owner ) : m_map( map ), m_owner( owner )
{
}

t_adventure_ai const* t_ai_army::get_ai() const
{
	return &m_map->get_ai();
}

t_adventure_map* t_ai_army::get_map() const
{
	return m_map;
}

int t_ai_army::get_owner_number() const
{
	if (m_map == NULL || m_owner == NULL)
		return -1;
	
	return m_map->get_player_number( m_owner->get_color() );
}


struct t_creation_info 
{
	t_creation_info( t_town_ptr town );
	t_creation_info( t_creation_info const & source_info );

	void	cache_garrison( float value_of_garrison );

	t_town_ptr							town_ptr;
	t_shared_ptr<t_creature_purchaser>	purchaser_ptr;
	t_shared_ptr<t_creature_array> 		army_ptr;
	float								value;

};

t_creation_info::t_creation_info( t_creation_info const & source_info )
{
	town_ptr = source_info.town_ptr;
	value = source_info.value;
	purchaser_ptr = source_info.purchaser_ptr;
	army_ptr = source_info.army_ptr;
}

t_creation_info::t_creation_info( t_town_ptr town )
	: town_ptr(town)
{
	army_ptr = new t_ai_army( town_ptr->get_map(), town->get_owner() );
	purchaser_ptr = new t_creature_purchaser( *town_ptr );
	purchaser_ptr->go_shopping( *town_ptr, town_ptr->get_garrison(), NULL, true );
}

void t_creation_info::cache_garrison( float value_of_garrison )
{
	army_ptr->swap_creatures( town_ptr->get_garrison() );
	value = value_of_garrison;
}

struct t_creation_comparison
{
	bool operator()( t_creation_info const& left, 
		             t_creation_info const& right ) const
	{
		return left.value > right.value;
	}
};


typedef std::list<t_creation_info> t_creation_list;

t_adventure_ai::t_adventure_ai(t_adventure_map& map) 
	: m_map(map), m_current_player(NULL), m_path_finder(map), 
		m_land_coverage(0.0f), m_rough_coverage(0.0f),
		m_spell_immunity_levels(0), m_buildable_mage_guild_level(-1),
		m_explored_once(false), m_logging(false), m_move_number(0),
		m_has_alt_dest(false), m_progress_handler(NULL),
		m_army_count(-1), m_last_army(NULL),
		m_hero_count(0), m_last_caravan_usage(-1), m_built_bounty(false),
		m_current_army(NULL), m_current_army_value(0.0f), 
		m_current_army_cache(NULL), m_current_army_danger( 0.0f ),
		m_current_army_in_danger(false), m_current_army_index(-1),
		m_current_team(-1), m_mover(NULL)

{
	// The map includes 2 layers for each level to hold pathing information for bridges.
	m_base_map_size = m_map.get_size();
	m_base_map_levels = m_map.get_num_levels();
	m_map_size = 2 * m_base_map_size * m_base_map_size * m_base_map_levels;

	m_boat_cost[k_gold] = 1000;
	m_boat_cost[k_wood] = 10;

	m_danger_map_ptr = new t_danger_map;
	if (m_logging)
	{
		m_log_file.open("ai_log.txt");
	}
}

t_adventure_ai::~t_adventure_ai()
{
}

void t_adventure_ai::do_turn( t_adventure_frame* frame )
{
	t_owned_ptr<t_override_input> input_override;

	if( get_enable_auto_play() )
	{
		input_override.reset( new t_override_input() );
	}

	t_game_application::set_cursor_visible( false );

	m_current_player = &m_map.get_current_player();
	if (!m_current_player->is_computer()) 
		return;

	declare_timer( timer_1, "t_adventure_ai::do_turn()" );

	m_current_team = m_current_player->get_team();

	t_player_color		player_color = m_current_player->get_color();
	t_ai_progress_bar* progress_bar = new t_ai_progress_bar( frame, 
										 k_player_color_keyword[player_color],
										 get_player_color_name( player_color ).c_str());
	m_progress_handler = progress_bar->get_handler();

	if (m_logging)
	{
		m_log_file << '<' << get_player_color_name( m_current_player->get_color() ) << ">\n";
		m_log_file.flush();
	}

	int save_team_number = -1;
	if (false) // Debug
	{
		save_team_number = get_enable_shroud() ? frame->get_map_window()->get_team_view() : -1;

		frame->set_team_view( m_current_team );
	}

	start_turn();

	t_creature_array*		last_army = m_current_army;
	t_adventure_object_ptr	last_object;
	
	if (last_army != 0)
		last_object = last_army->get_adventure_object();
	while ( !m_map.is_game_over() && get_next_army() ) 
	{
		move_current_army();
		m_data_cache.reset_army();
		m_move_number++;
		if (last_army != m_current_army && !m_map.is_game_over()) 
		{
			m_progress_handler->increment(1);
			last_army = m_current_army;
			if (last_army != 0)
				last_object = last_army->get_adventure_object();
		}
	}

	if (m_map.is_game_over())
		return;

	end_turn();

	if (m_logging)
	{
		m_log_file << "<**>\n";
		m_log_file.flush();
	}

	if (false) // debug
	{
		frame->set_team_view( save_team_number );
	}

	progress_bar->close();

	t_game_application::set_cursor_visible( true );
}

void t_adventure_ai::start_turn()
{
	declare_timer( timer, "t_adventure_ai::start_turn()");
	m_army_count = 0;
	m_hero_count = 0;
	m_last_army = NULL;
	m_single_threat = false;
	m_built_bounty = false;
	m_explored_once = false;
	
	m_current_player->ai_start_turn(m_map);

	count_assets();

	m_progress_handler->set_maximum( m_army_count + 1 );

	t_army_list::iterator 
		army_iter = m_map.get_armies_begin(),
		army_end = m_map.get_armies_end();

	while (army_iter != army_end)
	{
		t_army_ptr army_ptr = *army_iter++;
		army_ptr->get_creatures().ai_start_turn();
	}

	t_adventure_map::t_town_list::iterator
		town_iter = m_map.get_towns_begin(),
		town_end = m_map.get_towns_end();

	while (town_iter != town_end)
	{
		t_town_ptr town_ptr = *town_iter++;

		town_ptr->get_ai_town_data_cache()->start_turn();
		town_ptr->get_garrison().ai_start_turn();
	}

	t_ownable_garrisonable_adv_object_list::iterator
		iter = m_map.get_garrisons_begin(),
		end = m_map.get_garrisons_end();

	while (iter != end) 
	{
		(*iter++)->get_garrison().ai_start_turn();
	}


	calculate_threat();
	
	consider_army_creation();
}

void t_adventure_ai::count_assets()
{
	t_town_list& towns = *m_current_player->get_towns();
	t_town_list::iterator	iter = towns.begin(),
							iter_end = towns.end();

	while (iter != iter_end)
	{
		t_town_ptr town_ptr = *iter++;
		if (town_ptr->is_alive())
		{
			m_hero_count += count_heroes(&town_ptr->get_garrison());
			m_army_count++;
		}
	}

	t_army_array* actual_armies = m_current_player->get_armies();
	t_army_array::iterator  army_iter = actual_armies->begin(),
							army_end_iter = actual_armies->end();
	
	while (army_iter != army_end_iter)
	{
		t_army_ptr army_ptr = *army_iter++;
		if (!army_ptr->is_graveyard())
		{
			m_hero_count += count_heroes(&army_ptr->get_creatures());
			m_army_count++;
		}
	}
}

void t_adventure_ai::consider_army_creation()
{
	if (!can_create_army())
		return;

	t_town_list& towns = *m_current_player->get_towns();
	t_town_list::iterator	iter = towns.begin(),
							iter_end = towns.end();

	t_creation_list sorted_creation_list;

	while (iter != iter_end)
	{
		t_town_ptr town_ptr = *iter++;
		
		t_creature_array& garrison = town_ptr->get_garrison();
		if (!garrison.empty())
			continue;

		t_adv_map_point point;
		if ( !garrison.get_virtual_position( point ) )
			continue;
		
		t_creation_info creation_info( town_ptr );

		if (town_ptr->get_garrison().empty())
			continue;

		set_current_army( &garrison );
		
		int							max_distance = m_current_army->get_movement();
		t_adv_map_point				best_point;
		float						best_value;
		
		if ( ((m_map.get_day() % 3) == 0) || (m_army_count == 0) )
			max_distance = std::numeric_limits< int >::max();

		if (choose_destination( max_distance, best_point, best_value ))
		{
			creation_info.cache_garrison( best_value );
			t_creation_list::iterator 
				insert_iter = std::lower_bound( sorted_creation_list.begin(), sorted_creation_list.end(), creation_info, t_creation_comparison());
			sorted_creation_list.insert( insert_iter, creation_info );
		}
		else
			town_ptr->get_garrison().clear();

		set_current_army( NULL );
	}

	t_creation_list::iterator 
		creation_iter = sorted_creation_list.begin(),
		creation_end = sorted_creation_list.end();

	while ( (creation_iter != creation_end) && can_create_army() )
	{
		t_creation_info& info = *creation_iter++;
		if (m_current_player->ai_get_discretionary_funds() > info.purchaser_ptr->get_cost())
		{
			info.town_ptr->get_garrison().swap_creatures( *info.army_ptr );
			info.purchaser_ptr->apply_charges( *info.town_ptr );
		}	
	}
}

void t_adventure_ai::end_turn()
{
	reinforce_threatened_towns();

	m_current_player->ai_calculate_reserved_funds( m_map.get_day()+1 );

	consider_building_options();

	consider_caravans();

	clear_shipyards();
	
	m_data_cache.reset_player();
}

void t_adventure_ai::reinforce_threatened_towns()
{
	t_town_list* towns = m_current_player->get_towns();
	if (!towns) 
		return;

	t_town_list::iterator	iter = towns->begin(),
							end = towns->end();

//	update_invalidated_threat();

	// Add threatened towns in order of importance
	typedef std::vector<t_town_ptr> t_threatened_towns;
	t_threatened_towns threatened_towns;

	iter = towns->begin();
	while (iter != end)
	{
		t_town_ptr town_ptr = *iter++;		
		t_ai_town_data_cache* data = town_ptr->get_ai_town_data_cache();
		if (data->is_threatened()) 
		{
			t_threatened_towns::iterator 
				index = std::lower_bound( threatened_towns.begin(), threatened_towns.end(), town_ptr, t_compare_town_value( *this ) );
			threatened_towns.insert( index, town_ptr );
		}
	}

	t_threatened_towns::iterator	threat_iter = threatened_towns.begin(),
									threat_end_iter = threatened_towns.end();

	while (threat_iter != threat_end_iter )
	{
		t_town_ptr town_ptr = *threat_iter++;

		reinforce_threatened_town( town_ptr );
	}
}

void t_adventure_ai::reinforce_threatened_town( t_town_ptr town_ptr )
{
	t_ai_town_data_cache* data = town_ptr->get_ai_town_data_cache();
	t_ai_town_data_cache::t_threat_list threats;
	data->get_threat_list( threats, NULL );

	if (threats.empty()) 
		return; // Shouldn't occur.

	float value_drop;
	if (!town_ptr->empty() && survives_combat_series( &town_ptr->get_garrison(), &threats, value_drop ))
		return;

	for (t_town_building i = t_town_building(k_town_dwelling_8); i >= k_town_dwelling_1; enum_decr(i))
	{
		if (town_ptr->has(i)) 
		{
			t_creature_type creature_type = get_traits( town_ptr->get_type(), i ).creature;
			int population = town_ptr->get_population( creature_type );
			if (population)
			{
				t_creature_traits const& creature_traits = get_traits( creature_type );

				if (!town_ptr->can_add( creature_type ))
					continue;

				int can_afford = m_current_player->get_funds() / creature_traits.cost;
				if (can_afford > population)
					can_afford = population;

				town_ptr->hire_creatures( creature_type, can_afford );

				if (survives_combat_series( &town_ptr->get_garrison(), &threats, value_drop ))
					break;
			}
		}
	}

	// Make sure we stick around and defend
	town_ptr->get_garrison().get_ai_data_cache()->set_sleeping(true);
}

void t_adventure_ai::calculate_threat()
{
	t_player_list const& players = m_map.get_players();
	int size = players.size();
	t_adventure_path_finder threat_search( m_map );
	threat_search.set_path_type( k_path_search_ai_threat );

	t_army_list::iterator 
		iter = m_map.get_armies_begin(),
		end_iter = m_map.get_armies_end();

	while (iter != end_iter)
	{
		t_army_ptr army_ptr = *iter++;
		t_player* owner = army_ptr->get_owner();

		if ( ( army_ptr.get() == m_current_army ) 
				|| ( (owner != NULL) &&
					((owner->get_team() == m_current_player->get_team()) 
					|| owner->is_eliminated()) )
				|| army_ptr->empty()
				|| army_ptr->is_graveyard()
				|| ((owner == NULL) && (army_ptr->get_patrol_type() == -1)) )
			continue;

		t_visited_adv_points const& seeded_points = get_cache().get_danger_points( &m_map, army_ptr );
		for (t_visited_adv_points::const_iterator index = seeded_points.begin(); index != seeded_points.end(); ++index)
		{
			t_adv_map_point const& point = *index;
			t_adventure_object* object = m_map.get_trigger_object( point, army_ptr );
			if (object == NULL)
				continue;
			t_town* town = object->get_town();
			if ( (town != NULL) && (town->get_owner() == m_current_player) )
			{
				town->get_ai_town_data_cache()->inc_threat( town, army_ptr );
			}
		}
	} 

	t_caravan_set& caravans = m_map.get_caravans();
	t_caravan_set::iterator 
		caravan_iter = caravans.begin(),
		caravan_end = caravans.end();

	while (caravan_iter != caravan_end)
	{
		t_caravan_ptr& caravan_ptr = *caravan_iter++;
		
		if (caravan_ptr->get_owner() != m_current_player)
		{
			t_town_ptr dest_town_ptr = caravan_ptr->get_destination();
			if (dest_town_ptr->get_owner() == m_current_player)
			{
				dest_town_ptr->get_ai_town_data_cache()->inc_threat( dest_town_ptr.get(), caravan_ptr.get() );
			}
		}
	}

	t_town_list& towns = *m_current_player->get_towns();
	t_town_list::iterator	town_iter = towns.begin(),
							town_iter_end = towns.end();

	while (town_iter != town_iter_end)
	{
		t_town* town = *town_iter++;
		t_ai_town_data_cache* cache = town->get_ai_town_data_cache();
		if (cache->is_threatened())
		{
			t_ai_town_data_cache::t_threat_list threats;
			cache->get_threat_list( threats, NULL );
			float value_drop = 0.0f;
			survives_combat_series( &town->get_garrison(), &threats, value_drop );
			cache->set_value_drop( value_drop );
		}
	}
}

void t_adventure_ai::update_invalidated_threat()
{
	t_town_list* towns = m_current_player->get_towns();
	t_town_list::iterator	iter = towns->begin(),
							end = towns->end();

	iter = towns->begin();
	while (iter != end)
	{
		t_town_ptr town_ptr = *iter++;		
		t_ai_town_data_cache* data = town_ptr->get_ai_town_data_cache();
		t_ai_town_data_cache::t_threat_list threats, invalidated;
		data->get_threat_list( threats, &invalidated );
	}
}

bool t_adventure_ai::get_next_army()
{
	clear_pending_messages();

	t_creature_array*	best_army = NULL;
	float				best_army_value = 0.0f;

	m_moving_last_army = true;

	if (m_has_alt_dest)
		return true;

	t_army_array* actual_armies = m_current_player->get_armies();
	if (actual_armies) 
	{
		t_army_array::iterator  army_iter = actual_armies->begin(),
								army_end_iter = actual_armies->end();
		while (army_iter != army_end_iter)
		{
			t_army_ptr army_ptr = *army_iter++;
			if (!army_ptr->is_graveyard())
			{
				best_army = determine_best_army( army_ptr->get_creatures(), best_army, best_army_value, m_moving_last_army );
			}
		}
	}

	if (can_create_army())
	{
		// Add town armies to the list.
		t_town_list* town_list = m_current_player->get_towns();
		t_town_list::iterator	town_iter = town_list->begin(),
								town_end = town_list->end();
		
		while (town_iter != town_end)
		{
			t_town_ptr town_ptr = *town_iter++;
			if (town_ptr->is_alive() && town_ptr->get_virtual_position( m_current_army_position ))
			{
				best_army = determine_best_army( town_ptr->get_garrison(), best_army, best_army_value, m_moving_last_army );
			}
		}
	}

	set_current_army( best_army );

	return (best_army != NULL);
}

void t_adventure_ai::move_current_army()
{
	assert(m_current_army);

	if (m_has_alt_dest)
	{
		if (m_logging)
		{
			m_log_file << "Moving to ALT\n";
		}
		attempt_move( m_alt_dest, false );
		m_has_alt_dest = false;
		return;
	}
	
	process_garrisoned_army();
	mark_shipyards();

	if (m_current_army_cache->is_sleeping())
		return;
	
	int max_distance = m_current_army->get_movement();
	bool complete_search = false;

	if ( (m_moving_last_army && !m_current_army_cache->has_moved_once()) || impending_defeat() || m_current_army_in_danger )
	{
		complete_search = true;
		max_distance = std::numeric_limits< int >::max();
	}

	if (m_moving_last_army)
		m_last_army = m_current_army;

	t_adv_map_point				best_point;
	float actual_value;
	for (int i = 0; i < k_ai_max_turns_of_move_eval; i++) 
	{
		if (choose_destination( max_distance, best_point, actual_value ))
		{
			if (m_current_army_cache->is_sleeping())
				return;

			if (!m_explored_once)
			{
				t_adventure_tile const& tile = m_map.get_adv_tile( best_point );
				bool never_explored = ( tile.get_visibility( m_current_team ) == k_tile_never_explored );
				if (never_explored)
					m_explored_once = true;
			}

			t_adventure_path_data& data = m_path_finder.get_existing_data( best_point );
			m_current_army_cache->set_target(best_point, actual_value, data.move_cost);
			bool consider_alt_dests = m_essential_dests.empty() 
										||
										(std::find(m_essential_dests.begin(), m_essential_dests.end(), best_point) == m_essential_dests.end());

			attempt_move( best_point, consider_alt_dests );

			bool moved_once = m_current_army_cache->has_moved_once();
			if ((m_current_army->get_position() == m_current_army_position) && moved_once)
				m_current_army_cache->set_sleeping(true);

			return;
		}
		
		if ( m_current_army_cache->is_sleeping() || complete_search )
			break;

		if ((i > 2) && m_current_army_cache->has_moved_once())
			break;

		max_distance += m_current_army->get_max_movement() * 2;
	}	

	if (m_logging)
	{
		m_log_file << "Sleeping NVD\n";
	}
	m_current_army_cache->set_sleeping( true );
	m_current_army_cache->clear_target();
}

void t_adventure_ai::process_garrisoned_army()
{
	m_single_threat = m_threatened_town = false;
	m_our_threat = NULL;

	t_town* town = m_current_army->get_town();
	if (town)
	{
		if (town->get_ai_town_data_cache()->is_threatened())
		{
			m_threatened_town = true;
			t_ai_town_data_cache::t_threat_map const& threat_map = town->get_ai_town_data_cache()->get_threat_map();
			if (m_single_threat = (threat_map.size() == 1))
				m_our_threat = (threat_map.begin())->first;
			else
				m_current_army_cache->set_sleeping(true);
		}

		t_adv_map_point location;
		if (town->find_adjacent_space( location, *m_current_army ))
		{
			t_ai_army visitor( town->get_map(), town->get_owner() );		
			supplement_army( *town, town->get_garrison(), visitor );
			if (!visitor.empty())
			{
				t_army_ptr new_army = new t_army( &visitor );
				new_army->set_owner( m_map.get_player_number( m_current_player->get_color() ) );
				new_army->place( m_map, location );
				new_army->trigger_events();
			}
		}
		else
		{
			t_creature_purchaser purchaser( *town, town->get_garrison(), NULL, true );
			purchaser.go_shopping( *town, town->get_garrison(), NULL );
			m_current_army_cache->set_sleeping(true);
		}
	}
}

t_army* t_adventure_ai::get_army()
{
	t_army* army = m_current_army->get_army();
	if (army == NULL)
	{
		if (!can_create_army())
			return NULL;

		t_adventure_object* object = m_current_army->get_adventure_object();
		if (object) {
			t_adv_map_point location;
			if (object->find_adjacent_space( location, *m_current_army ))
			{
				t_army_ptr new_army = new t_army( m_current_army );
				m_current_army->set_ai_data_cache( new t_ai_army_data_cache() );
				new_army->set_owner( m_map.get_player_number( m_current_player->get_color() ) );
				new_army->place( m_map, location );

				// Too many temporary armies to risk this
				// new_army->trigger_events();
				return new_army;
			}
		}
		assert(false);
		return NULL;
	}
	else
	{
		return army;
	}
}

void t_adventure_ai::clear_distance_map()
{
	m_distance_map.assign(m_map_size, std::numeric_limits< t_uint16 >::max());
}

void t_adventure_ai::clear_danger_map()
{
	declare_timer(timer, "t_adventure_ai::clear_danger_map()" );
	m_danger_map_ptr->assign(m_map_size, 0);	
}

void t_adventure_ai::clear_value_map()
{
	m_value_map.assign(m_map_size, 0.0f);	
}

void t_adventure_ai::get_point_indices( t_adv_map_point const& point, int& danger_index, int& point_index )
{
	t_adventure_path_data& data = m_path_finder.get_existing_data(point);

	if (m_map.is_blocked(point) && m_map.is_trigger(point))
	{
		if (data.step_count == 1)
			danger_index = m_current_army_index;
		else
			danger_index = get_map_index( m_map, data.last_point );

		point_index = get_map_index( m_map, point );
	}
	else 
	{
		point_index = danger_index = get_map_index(m_map, point);
	}
}

float t_adventure_ai::calculate_value_of_location( t_adv_map_point const& point )
{
	int danger_index, index;
	get_point_indices( point, danger_index, index );

	t_adventure_path_data& data = m_path_finder.get_existing_data(point);

	if (!m_essential_dests.empty())
	{
		if (std::find(m_essential_dests.begin(), m_essential_dests.end(), point) != m_essential_dests.end())
			return (data.value - (data.move_cost / 10000.0f));
	}

	float value_drop = (*m_danger_map_ptr)[danger_index];
	float total_drop = data.danger_value + value_drop;

	if (ignore_pathing_danger())
	{
		if (value_drop < 0.95f)
			return (m_value_map[ index ] * k_ai_move_value_multiplier) / data.move_cost;
		else
			return 0.0f;
	}
	else
		if (total_drop >= 0.95f)
		{
//			if ( (data.danger_value >= 0.95f) 
//				|| ( (m_current_army->get_movement() >> 2) > data.move_cost ) )
				return 0.0f;
		}

	float value_loss = total_drop * m_current_army_value;

	if ((data.value - value_loss) < 0.0f)
		return 0.0f;

	float adjusted_value = m_value_map[ index ] - value_loss;
//	float adjusted_value = data.value - value_loss;

	if ((point == m_current_army_cache->get_target()) && (adjusted_value > 0.0f))
		adjusted_value += k_ai_value_of_continuation;

	return ((adjusted_value * k_ai_move_value_multiplier) / data.move_cost);
}

bool t_adventure_ai::choose_destination(int max_distance, t_adv_map_point& best_destination, float& best_value )
{
	declare_timer( timer_1, "t_adventure_ai::choose_destination()");

	t_map_point_array destinations;
	find_potential_destinations( destinations, max_distance );

	if (m_current_army_cache->is_sleeping())
		return false;

	best_value = 0.0f;
	int size = destinations.size();
	int best_index = -1;
	for (int i = 0; i < size; i++) {
		float value = calculate_value_of_location(destinations[i]);

		if (value > best_value) {
			best_value = value;
			best_index = i;
		}
	}

	if (best_index == -1) 
	{
		m_log_file << "Picked: (none)\n";
		m_log_file.flush();
		return false;
	}

	best_destination = destinations[best_index];

	if (m_logging)
	{
		int index = get_map_index(m_map, best_destination);
		float value_drop = (*m_danger_map_ptr)[index];
		t_adventure_path_data& data = m_path_finder.get_existing_data(best_destination);
		m_log_file << format_string("Picked: (%d,%d,%d) - MC:%d V:%.2f DV:%.2f MDV:%.2f\n", best_destination.row, best_destination.column, best_destination.level, data.move_cost, best_value, value_drop, data.danger_value);
		m_log_file.flush();
	}

	return true;
}

void t_adventure_ai::mark_object_on_value_map( t_adventure_object const& object, float value )
{
	t_visited_adv_points const& seeded_points = get_cache().get_value_points( &m_map, &object, m_current_player );

	t_visited_adv_points::const_iterator index;
	
	for (index = seeded_points.begin(); index != seeded_points.end(); ++index) 
	{
		m_value_map[get_map_index(m_map, *index)] += value;
	}
}

void t_adventure_ai::find_potential_destinations( t_map_point_array& destinations, int max_distance, bool alt_dest )
{
	declare_timer( timer_1, "t_adventure_ai::find_potential_destinations()");
	
	t_town* town = NULL;

	clear_pending_messages();
	m_essential_dests.clear();

	if (!alt_dest)
		clear_value_map();
	
	t_visited_adv_points	visited, escape_points, explore_points;
	m_path_finder.set_path_type( k_path_search_ai );
	m_path_finder.set_army( m_current_army );
	m_path_finder.set_danger_map( m_danger_map_ptr );
	m_path_finder.seed_position( visited, max_distance );

	declare_timer( timer_2, "t_adventure_ai::find_potential_destinations() post path");

//	build_distance_map();

	bool dangerous_positioning = m_current_army_danger > 0.20f;
	for (t_visited_adv_points::iterator it = visited.begin(); it != visited.end(); ++it )
	{
		t_adv_map_point& point = *it;
		t_adventure_path_data& path_data = m_path_finder.get_existing_data( point );

		// We'll let the closest army have a valuable destination, unless we're currently in danger.
		int index = get_map_index(m_map, point);

		if ( (point == m_current_army_position) 
			|| !m_current_army->is_in_patrol_radius( point ) )
			continue;
		
		t_adventure_tile const& tile = m_map.get_adv_tile( point );

		float danger_value_drop = (*m_danger_map_ptr)[index];
		float value_drop = danger_value_drop + path_data.danger_value;
		bool dangerous_dest = value_drop > 0.95f;

		bool is_trigger = tile.is_trigger( point.on_bridge );

		if (!is_trigger 
				&& ( ( dangerous_positioning && !dangerous_dest ) || ( m_current_army_in_danger && (danger_value_drop < 1.0f) ) )
				&& !m_single_threat )

		{
			escape_points.push_back( point );
			continue;
		} 

		bool never_explored = ( tile.get_visibility( m_current_team ) == k_tile_never_explored );
		if ( never_explored && !dangerous_dest && !m_single_threat )
		{
						
			if (is_trigger)
				continue;

			explore_points.push_back( point );
			continue;
		}

		if (!is_trigger || never_explored)
			continue;


		t_adventure_object* object = m_map.get_trigger_object( path_data.last_point, 
	                                                     path_data.direction,
	                                                     m_current_army);

		if ( (object == NULL) || ( m_current_army->get_adventure_object() == object ) )
			continue;

		path_data.value = object->ai_value( *this, *m_current_army, path_data.move_cost );

		if ((path_data.value > 0.0f) && (!alt_dest))
			mark_object_on_value_map( *object, path_data.value );

		if (m_moving_last_army)
		{
			town = object->get_town();
			if  ((town != NULL) 
					&& (m_current_player == town->get_owner()) 
					&& town->has( k_town_caravan ) )
				m_current_army_cache->compare_nearest_town( town, path_data.move_cost );
		}

		if (town = object->get_town())
		{
			t_ai_town_data_cache* cache = town->get_ai_town_data_cache();
			if ( impending_defeat() 
					||	(cache->is_threatened() 
							&& (cache->get_value_drop() >= 0.95f)) )
			{ 
				
				m_essential_dests.push_back( point );
				destinations.push_back( point );
				continue;
			}
		}

		if (dangerous_dest)
		{
			
			if ( !m_threatened_town || ( object->get_creature_array() != m_our_threat ) )
				continue;

			m_current_army_cache->set_sleeping(true);

			return;
		} 
		else
		{
			if ( m_threatened_town )
			{
				if ( object->get_creature_array() != m_our_threat )
					continue;

				m_essential_dests.push_back( point );
				destinations.push_back( point );
			}
		}


		if (m_logging)
		{
			m_log_file << format_string( "  (%3d,%3d,%3d) - V:%.2f ", point.row, point.column, point.level, path_data.value );
			if (path_data.barrier_value != 0.0f)
				m_log_file << format_string("BV:%.2f ", path_data.barrier_value);

			if (value_drop != 0.0f)
				m_log_file << format_string("DV:%.2f ", value_drop );
			
			if (path_data.danger_value != 0.0f)
				m_log_file << format_string("MDV:%.2f ", path_data.danger_value );

			m_log_file << '\n';
			m_log_file.flush();
		}

//		if (is_expendable_object( object ) && (path_data.move_cost > m_distance_map[index]))
//			continue;

		if (path_data.value > 0.0f)
			destinations.push_back( point );
	}

	for (t_visited_adv_points::iterator it = escape_points.begin(); it != escape_points.end(); ++it)
	{
		t_adv_map_point& point = *it;
		t_adventure_path_data& path_data = m_path_finder.get_existing_data( point );

		if (!path_data.actual_enemy_adjacent)
		{
			int index = get_map_index(m_map, point);
			path_data.value = m_value_map[index] = k_ai_danger_escape_value;
			destinations.push_back( point );
		}
	}

	for (t_visited_adv_points::iterator it = explore_points.begin(); it != explore_points.end(); ++it)

	{
		t_adv_map_point& point = *it;
		t_adventure_path_data& path_data = m_path_finder.get_existing_data( point );

		float value = !m_explored_once ? k_ai_high_exploration_value : k_ai_low_exploration_value;
		int index = get_map_index(m_map, point);
		path_data.value = m_value_map[index] = value;

		destinations.push_back( point );
	} 
}

void t_adventure_ai::build_distance_map()
{
	clear_distance_map();

	t_army_array* armies = m_current_player->get_armies();

	t_army_array::iterator 
		army_index = armies->begin(),
		army_end = armies->end();
	
	while (army_index != army_end) 
	{
		clear_pending_messages();
	
		t_army* friendly_army = *army_index++;

		if (friendly_army == m_current_army) 
			continue;

		mark_army_on_distance_map( friendly_army );
	}
}

void t_adventure_ai::mark_army_on_distance_map( t_army* friendly_army )
{
	typedef t_adv_ai_data_cache::t_distance_points t_distance_points;
	typedef t_adv_ai_data_cache::t_distance_point t_distance_point;

	t_distance_points const& friendly_visited = get_cache().get_distance_points( &m_map, friendly_army->get_position(), 
																				 friendly_army->get_movement(), 
																				 friendly_army );

	for (t_distance_points::const_iterator index = friendly_visited.begin(); index != friendly_visited.end(); ++index ) 
	{
		t_distance_point const& point = *index;
		t_uint16& map_entry = m_distance_map[point.index];

		if ( point.distance < map_entry )
			map_entry = point.distance;
	}
}

void t_adventure_ai::build_danger_map()
{
	declare_timer( timer_1, "t_adventure_ai::build_danger_map()");
	
	clear_danger_map();

	t_army_list::iterator 
		iter = m_map.get_armies_begin(),
		end_iter = m_map.get_armies_end();

	while (iter != end_iter)
	{
		clear_pending_messages();

		t_army_ptr army_ptr = *iter++;

		if ( skip_danger_validation( army_ptr.get() ) )
			continue;
		
		mark_army_on_danger_map( army_ptr.get(), !m_built_bounty );
	}

	t_adventure_map::t_town_list::iterator 
		town_iter = m_map.get_towns_begin(),
		town_end = m_map.get_towns_end();

	while (town_iter != town_end)
	{
		clear_pending_messages();

		t_creature_array* army = &(*town_iter++)->get_garrison();

		if ( skip_danger_validation( army ) )
			continue;
		
		mark_army_on_danger_map( army, !m_built_bounty );
	}

	int player_cnt = m_map.get_player_count();
	for (int i = 0; i < player_cnt; i++)
	{
		t_player* player = &m_map.get_player( i );
		if ( same_team( player, m_current_player) || player->is_eliminated() ) 
			continue;
		
		t_garrison_list garrisons = player->get_garrisons();

		t_garrison_list::iterator 
			iter = garrisons.begin(),
			end_iter = garrisons.end();

		while (iter != end_iter)
		{
			clear_pending_messages();

			t_creature_array* army = &(*iter++)->get_garrison();
			if ( skip_danger_validation( army ) )
				continue;

			mark_army_on_danger_map( army, !m_built_bounty );
		}
	}

	m_built_bounty = true;
}

bool t_adventure_ai::skip_danger_validation( t_creature_array* army ) const
{
	t_player* owner = army->get_owner();

	return ( ( army == m_current_army ) 
				|| ( (owner != NULL) &&
					((owner->get_team() == m_current_team) 
					|| owner->is_eliminated() ) )
					|| army->is_graveyard() 				
					|| !army->is_alive()
				);
}


void t_adventure_ai::mark_army_on_danger_map(t_creature_array* enemy_army, bool build_bounty )
{
	float value_drop = value_lost_in_combat( m_current_army, enemy_army );
	if (value_drop == 0.0f)
		return;

	t_visited_adv_points const& seeded_points = get_cache().get_danger_points( &m_map, enemy_army );

	t_visited_adv_points::const_iterator 
		index = seeded_points.begin(),
		index_end = seeded_points.end();
	while (index != index_end) 
	{
		t_adv_map_point const& point = *index++;
		int index = ( (point.on_bridge * m_base_map_levels + point.level) * m_base_map_size + point.row )
						* m_base_map_size + point.column;
		(*m_danger_map_ptr)[index] += value_drop;
		
		if (build_bounty)
		{
			t_adventure_object*	object = m_map.get_trigger_object( point, enemy_army );
			if (object && (object->get_owner() == m_current_player) )
			{
				if (enemy_army->get_owner() != NULL)
				{
					float bounty_value = object->ai_value( *this, *enemy_army, 1 );
					enemy_army->get_ai_data_cache()->increment_bounty( bounty_value );
				}
			}
		}
	}
}

void t_adventure_ai::mark_shipyards()
{
	clear_shipyards();

	// If the player doesn't have the funds to buy a boat, don't bother continuing.
	t_player* player = m_current_player;

	m_ship_construction_barrier = (player->get_material_values() * m_boat_cost).get_sum();

	if (player->get_funds() < m_boat_cost) return;

	// Iterate thru all shipyards (including those we don't own) and mark
	// its boat output location.
	t_shipyard_list& shipyards = m_map.get_shipyards();
	t_shipyard_list::iterator 
			iter = shipyards.begin(),
			end = shipyards.end();
	t_adv_map_point ship_position;

	while (iter != end) 
	{
		t_shipyard_ptr shipyard_ptr = *iter++;
	
		if (!shipyard_ptr->find_new_ship_position( ship_position )) 
			continue;

		if (same_team(shipyard_ptr->get_owner(), player))
		{
			t_adventure_tile& tile = m_map.get_adv_tile(ship_position);
			tile.ai_set_can_build_ship( true, shipyard_ptr->get_map_id() );
			m_marked_ships.push_back(&tile);
		}
	}

	// Iterate thru owned towns and mark their product boat location, assuming
	// they either have a shipyard or could have one in a single purchasing step.
	t_town_list* towns = player->get_towns();
	if (towns == NULL) return;
	int size = towns->size();
	for (int i = 0; i < size; i++) 
	{
		t_town_ptr town_ptr = (*towns)[i];
		bool has_shipyard = town_ptr->has( k_town_shipyard ) ;
		if ( has_shipyard
				|| (town_ptr->can_build(k_town_shipyard) 
					&& town_ptr->is_enabled(k_town_shipyard)
					&& !town_ptr->has_built()) )
		{
			t_building_traits const&	traits = get_traits( town_ptr->get_type(), k_town_shipyard );
			t_material_array			build_cost = m_boat_cost;
			if (!has_shipyard)
				build_cost += traits.cost;

			if (player->get_funds() <= build_cost)
				continue;

			t_adv_map_point ship_position;
			if (town_ptr->find_new_ship_position( ship_position, false )) {
				t_adventure_tile& tile = m_map.get_adv_tile(ship_position);
				tile.ai_set_can_build_ship( true, town_ptr->get_map_id() );
				m_marked_ships.push_back(&tile);
			}
		}
	}
}

void t_adventure_ai::clear_shipyards()
{
	while( !m_marked_ships.empty() )
	{
		t_adventure_tile* tile = m_marked_ships.back();
		m_marked_ships.pop_back();
		tile->ai_set_can_build_ship( false, -1 );
	}
}

void t_adventure_ai::trim_path( t_adv_map_point const& destination )
{
	int		move_left = m_current_army->get_movement();
	float	value_drop = m_current_army_danger + m_path_finder.get_existing_data(m_current_army_position).danger_value;
	bool	in_danger = value_drop >= 1.0f;   
	int		safe_point = -1;

	int first_point = m_current_path.size() - 1;
  int i;
	for (i = first_point; i >= 0; i--)
	{
		t_adventure_path_point& point = m_current_path[i];

		int index = get_map_index(m_map, point);
		t_adventure_path_data const& data = m_path_finder.get_existing_data(point);
		value_drop = (*m_danger_map_ptr)[index] + data.danger_value;
		bool entering_danger = (value_drop >= 1.0f);

		bool is_trigger = m_map.get_trigger_object( point, data.direction, m_current_army ) != NULL;
		if ( (point.move_cost > move_left) || is_trigger )
		{
			if (i == first_point) 
			{
				if (!in_danger && (entering_danger || is_trigger))
				{
					m_current_army_cache->set_sleeping(true);

					if (m_logging)
						m_log_file << "Sleeping - 1 step danger";
				}
				return;
			}
			else
				if (in_danger)
					break;
				else
					// We've run out of mps, but not in danger...  Allow the move underhindered.
					return;
		}

		if (!entering_danger)
			safe_point = i;
		
		in_danger = entering_danger;
	}

	log_path( safe_point );
	
	apply_trim( safe_point, i, destination  );
}

void t_adventure_ai::apply_trim( int safe_point, int stop_point, t_adv_map_point const& destination )
{
	if ( (safe_point == 0) 
			|| impending_defeat() 
			|| ignore_pathing_danger())
		return;

	// Handle the situation where there is no safe point along this path.
	if (safe_point == -1)
	{
		// If we're going to actually make it to the destination, let's see if it's allowable to 
		// ignore the danger.
		if (stop_point == -1)
		{
			if ( std::find(m_essential_dests.begin(), m_essential_dests.end(), destination) != m_essential_dests.end() ) 		
				return;

			t_adventure_object* trigger = m_map.get_trigger_object( m_current_path[0], m_current_army );
			if (trigger == NULL) 
				return;
			
			t_town* town = trigger->get_town();
			if ( (town 
					&& town->get_ai_town_data_cache()->is_threatened()) 
					|| m_current_army_cache->get_urgent_target() )
				return;
		}
		else
		{
			m_current_army_cache->set_sleeping(true);
			if (m_logging)
			{
				m_log_file << "Sleep - (No safe step)\n";
			}
			return;
		}
	}

	// m_current_path.erase(&m_current_path[0], &m_current_path[safe_point]);
  m_current_path.erase(m_current_path.begin(), m_current_path.begin() + safe_point);
}

void t_adventure_ai::log_path( int safe_point )
{
	if (m_logging)
	{
		m_log_file << "Path: ";
		int size = m_current_path.size();
		for (int i = 0; i < size; i++)
		{
			t_adventure_path_point const& point = m_current_path[i];
			int index = get_map_index(m_map, point);
			float value_drop = (*m_danger_map_ptr)[index];
			m_log_file << format_string("[(%d,%d,%d) MC:%u AMC:%u MR:%u DV:%.2f MDV:%.2f)] ", point.row, point.column, point.level,
										 point.move_cost, point.adjusted_move_cost, point.move_remaining, value_drop, point.danger_value );
		}
		m_log_file << '\n';
		if (safe_point != -1)
		{
			m_log_file << format_string( "Triming path: %d\n", safe_point );
		}
		m_log_file.flush();
	}

}

void t_adventure_ai::halt_movement()
{
	if (m_mover.get() != NULL)
		m_mover->cancel_move();
}

void t_adventure_ai::attempt_move( t_adv_map_point const& point, bool consider_alt_dests )
{
	declare_timer( timer_1, "t_adventure_ai::attempt_move()");
	
	t_adventure_map_ptr const map = &m_map;	// this is merely to hold a reference to the adventure map so it doesn't close 

	t_army* actual_army = get_army();

	if (actual_army == NULL)
	{
		m_current_army_cache->set_sleeping(true);
		return;
	}

	if (actual_army->get_creature_array() != m_current_army)
		set_current_army( actual_army, false );

	m_current_army_cache->set_moved_once( true );
	m_path_finder.get_path(point, m_current_path);

	trim_path( point );
	
	actual_army->set_path(m_current_path);

	{
		declare_timer( timer_2, "t_adventure_ai::attempt_move() entire move");
		m_mover = new t_ai_army_mover(actual_army->get_map_window(), actual_army, this, &m_path_finder, consider_alt_dests);

		// run the first idle before entering loop
		m_mover->on_idle();
		while ( !m_map.is_game_over() 
				&& (!m_mover->is_done() || m_map.get_map_window()->enemy_is_moving()) ) 
		{
			process_message();
		}
	}

	if (m_map.is_game_over())
		return;

	if (m_has_alt_dest)
	{
		if (m_logging)
			m_log_file << format_string("Picked alt dest: (%d,%d,%d)\n", m_alt_dest.row, m_alt_dest.column, m_alt_dest.level);	
		m_mover = NULL;
		return;
	}

	if ( m_mover->is_multiple_turn_move() 
			&& m_current_army->get_position() == m_mover->get_actual_destination() )
	{
		if (m_logging)
		{
			m_log_file << "Sleeping MTM\n";
		}
		m_current_army_cache->set_sleeping( true );
	}

	if (m_logging)
	{
		t_adv_map_point const& cur_position = m_current_army->get_position();
		int index = get_map_index(m_map, cur_position);
		float value_drop = (*m_danger_map_ptr)[index];
		m_log_file << "MPs Remaining : " << m_current_army->get_movement() 
			<< format_string(" DV: %.2f (%d,%d,%d) Sleeping: %d ", 
								value_drop, cur_position.row, cur_position.column, cur_position.level,
								m_current_army_cache->is_sleeping() ? 1 : 0 ) 
			<< '\n';
		
		m_log_file.flush();
	}

	m_mover = NULL;

	clear_pending_messages();
}

float t_adventure_ai::scale_for_aggression( t_player const* source, t_player const* destination ) const
{
	if ((destination != NULL) && (source != NULL) && (source->get_team() == destination->get_team()))
		return 0.0f;

	return 1.0f;
}

float t_adventure_ai::scale_for_combat_aggression( t_player const* source, t_player const* destination ) const
{
	if ( (source && destination 
			&& (source->get_team() == destination->get_team()))
		|| ((source == NULL) && (destination == NULL)) )
		return 0.0f;

	return 1.0f;
}

float t_adventure_ai::get_land_coverage() const
{
	return m_land_coverage;
}

void t_adventure_ai::reset_danger()
{
	m_data_cache.reset_danger();
}

void t_adventure_ai::start_game() 
{
	build_damage_spell_list();
	calculate_land_coverage();
	calculate_spell_immunity_levels();
}

void t_adventure_ai::calculate_spell_immunity_levels()
{
	for( t_spell spell = enum_add(k_spell_none, 1); spell < k_spell_count; enum_incr( spell ) )
	{
		t_ai_spell_type type = get_ai_spell_type( spell );		
		if ((type == k_ai_spell_type_blessing) 
			|| (type == k_ai_spell_type_summoning) 
			|| (type == k_ai_spell_type_healing) )
			continue;
		m_spell_immunity_levels += get_spell_level( spell );
	}
}

void t_adventure_ai::calculate_land_coverage()
{
	float land_tiles = 0;
	float rough_tiles = 0;
	int total_tiles = 0;

	int map_size = m_map.get_size();
	int map_levels = m_map.get_num_levels();
	t_adv_map_point	point;
	for (point.level = 0; point.level < map_levels; point.level++)
	{
		for (point.row = 0; point.row < map_size; point.row++)
		{
			int col_end = m_map.get_row_end( point.row );
			for (point.column = m_map.get_row_start( point.row ); point.column < col_end; point.column++)
			{
				t_adventure_tile const& tile = m_map.get_adv_tile(point);
				if (tile.is_blocked( point.on_bridge )) continue;
			
				total_tiles++;

				if (get_terrain_cost(tile.get_terrain()) > 100) 
					rough_tiles++;
				if (m_map.is_land(point))
					land_tiles++;
			}
		}
	}
	m_land_coverage = land_tiles / total_tiles;
	m_rough_coverage = rough_tiles / total_tiles;
}

const int k_adventure_ai_save_version = 1;

bool t_adventure_ai::read( std::streambuf& stream, int version )
{
	if (version < 15) 
	{
		calculate_land_coverage();
		return true;
	}

	int ai_version = ::get<t_uint8>( stream ); 

	m_land_coverage = ::get<float>( stream );

	if (ai_version < 1)
	{
		m_spell_immunity_levels = 1;
	}
	else
	{
		m_spell_immunity_levels = ::get<int>( stream );
	}
	
	return true;
}

bool t_adventure_ai::write( std::streambuf& stream ) const 
{
	put<t_uint8>( stream, k_adventure_ai_save_version );

	put<float>( stream, m_land_coverage );

	put<int>( stream, m_spell_immunity_levels );

	return true;
}

float t_adventure_ai::get_rough_coverage() const
{
	return m_rough_coverage;
}

int t_adventure_ai::get_spell_immunity_levels() const
{
	return m_spell_immunity_levels;
}

void t_adventure_ai::build_damage_spell_list()
{
	for (t_spell spell = enum_add(k_spell_none, 1); spell < k_spell_count; enum_incr(spell))
	{
		if (get_ai_spell_type(spell) == k_ai_spell_type_damage)
			m_damage_spells.push_back(spell);
	}
}

t_adventure_ai::t_damage_spells const& t_adventure_ai::get_damage_spells() const
{
	return m_damage_spells;
}

int t_adventure_ai::get_buildable_mage_guild_level() const
{
	return m_buildable_mage_guild_level;
}

int t_adventure_ai::get_mage_guild_level() const
{
	return (m_buildable_mage_guild_level > 1) ? m_buildable_mage_guild_level - 1 : 0;
}

void t_adventure_ai::calculate_mage_guild_level()
{
	int buildable_level = -1;

	t_town_list* towns = m_current_player->get_towns();
	if (towns == NULL) return;
	int size = towns->size();
	for (int i = 0; (i < size) && (buildable_level < 5); i++) 
	{
		t_town_ptr town_ptr = (*towns)[i];
		
		for (int i = buildable_level + 1; i < 5; i++)
		{
			if (town_ptr->can_build(enum_add(k_town_mage_guild_1, i)))
				buildable_level = i;
		}
	}
	m_buildable_mage_guild_level = buildable_level + 1;
}

void t_adventure_ai::do_neutral_player()
{
	t_owned_ptr<t_override_input> input_override;

	if( get_enable_auto_play() )
	{
		input_override.reset( new t_override_input() );
	}

	t_game_application::set_cursor_visible( false );

	int save_player_number = m_map.get_player_number();

	t_army_list::iterator army_iter = m_map.get_armies_begin();

	// note: it's important to leave the iterator on a neutral army,
	// because other armies can be deleted from the list as a result of processing
	// a neutral army.

	// find the first neutral army that is not a graveyard
	while (army_iter != m_map.get_armies_end()
		   && ((*army_iter)->get_owner() != 0 || (*army_iter)->is_graveyard()))
		++army_iter;

	while ( !m_map.is_game_over() && army_iter != m_map.get_armies_end() )
	{
		t_army_ptr army_ptr = *army_iter;	

		// find the next neutral army that is not a graveyard.
		do
		{
			++army_iter;
		} while (army_iter != m_map.get_armies_end()
			     && ((*army_iter)->get_owner() != 0 || (*army_iter)->is_graveyard()));

		t_patrol_type type = army_ptr->get_patrol_type();

		if (type == k_patrol_guard)
		{
			if (m_map.guards_can_move())
				process_guarding_army( *army_ptr );
		}
		else
			process_wandering_army( *army_ptr );
	}

	if (!m_map.is_game_over() && m_map.is_hotseat())
		m_map.set_player(save_player_number);

	t_game_application::set_cursor_visible( true );
}

void t_adventure_ai::process_wandering_army( t_army& army )
{
	int					direction = army.ai_get_wander_direction();
	t_adv_map_point		previous_point = army.get_position();
	t_wander_target		wander_target;
	int					range = army.get_movement() / 2;
	bool				wander_again;
	int					dominate_direction;
	int					wander_count = 0;

	// Attempt to wander until we find a suitable direction.
	do {
		wander_again = false;
		
		bool randomize = random(0, 3) == 0;
		wander_target = select_wandering_destination( army, direction, range, false, randomize, dominate_direction );

		if (wander_target == k_wander_target_none) 
		{
			// If we had a specific direction in mind, clear our preference and try again.
			if (direction != -1)
			{
				direction = dominate_direction;
				army.ai_set_wander_direction(direction);
				wander_again = true;
				continue;
			} 
			else
				break;  // This shouldn't happen unless a map designer penned in an army.
		} 
		else 
		{
			if (randomize)
			{
				t_adventure_path const& path = army.get_path();
				if (path.size())
				{
					int col_distance = path[0].column - previous_point.column;
					int row_distance = path[0].row - previous_point.row; 
					double radian_direction;
					direction = offset_to_direction( col_distance, row_distance, radian_direction );
				}
			}
			else
				if (direction == -1)
				{
					direction = dominate_direction;
				}
		}
	} while (wander_again && (wander_count++ < 2));

	// If the target is random, consider just relaxing for a turn.
	int idle_odds = (army.get_patrol_radius() == -1) ? 3 : 2;
	if ((wander_target == k_wander_target_tile) && (random(0, idle_odds) == 0))
		return;

	t_adventure_path const& path = army.get_path();

	if ((path.size() != 0) && path[0] != army.get_position())
	{
		t_counted_ptr<t_army_mover> mover = new t_army_mover(army.get_map_window(), &army);
		while (!mover->is_done())
		{
			process_message();
		}
	}

	// If we were randomly wandering do a scan for a new target object
	if (wander_target == k_wander_target_tile) 
	{
		t_wander_target scan_target = select_wandering_destination( army, direction, range, true, false, dominate_direction );
		if (scan_target == k_wander_target_object)
		{
			t_counted_ptr<t_army_mover> mover = new t_army_mover(army.get_map_window(), &army);
			while (!mover->is_done())
			{
				process_message();
			}
		}
	}

	army.ai_set_wander_direction( direction );
}

t_adventure_ai::t_wander_target t_adventure_ai::select_wandering_destination( t_army& army, 
																				int direction, int range, 
																				bool only_targets, 
																				bool randomize_direction, 
																				int& dominate_direction)
{
	static const int visibility_range = 6;
	static const int visibility_distance = visibility_range * visibility_range;
	
	dominate_direction = -1;

	t_visited_adv_points	visited_points;
	t_adventure_path_finder path_search( m_map );
	path_search.set_army( &army );
	path_search.set_path_type( k_path_search_ai_neutral_army );
	path_search.seed_position( visited_points, range );

	t_adv_map_point origin_point = army.get_position();
	t_adv_map_point destination;
	
	t_map_point_array potential_destinations;
	t_map_point_array sorted_destinations[8];
	int								closest_trigger = -1;
	t_player*						targeted_player = NULL;
	int								direction_counter[8];

	std::fill(&direction_counter[0], &direction_counter[8], 0);

	for (t_visited_adv_points::iterator index = visited_points.begin(); index != visited_points.end(); ++index)
	{
		t_adv_map_point& point = *index;
		t_adventure_path_data& path_data = path_search.get_existing_data( point );

		// Make sure this point is in the viewable map.
		if ( (point.column < m_map.get_row_start( point.row )) || (point.column >= m_map.get_row_end( point.row )) )
			continue;

		// If we've already picked a closer target, skip this point.
		if ((closest_trigger != -1) && (closest_trigger < path_data.move_cost))
			continue;

		// We can't see across gates to different levels
		if (origin_point.level != point.level) 
			continue;

		// Skip objects outside of our viewing radius
		// I am using the square distance (not a circular area) to improve the speed.
		int row_distance = point.row - origin_point.row;
		int col_distance = point.column - origin_point.column;
		if ((row_distance * row_distance + col_distance * col_distance) > visibility_distance)
			continue;

		// Ignore points outside of the patrol radius (if applicable)
		int patrol_radius = army.get_patrol_radius();
		if (patrol_radius != -1) 
		{
			patrol_radius *= patrol_radius;

			t_adv_map_point init_point = army.get_initial_location();
			int row_distance = point.row - init_point.row;
			int col_distance = point.column - init_point.column;
			if ((row_distance * row_distance + col_distance * col_distance) > patrol_radius)
				continue;
		}

		t_adventure_tile& tile = m_map.get_adv_tile(point);

		double target_direction;
		int integer_direction = offset_to_direction( col_distance, row_distance, target_direction );
		direction_counter[integer_direction]++;
			
		// If we're still interested in non-trigger tiles, add them to our list of destinations
		// Only add tiles that are in our desired wander direction.
		if (!tile.is_trigger( point.on_bridge )) 
		{
			if (only_targets || (closest_trigger != -1) || path_data.actual_enemy_adjacent) continue;

			if ((direction != -1) && (!randomize_direction))
			{
				// Skip this square if it's outside our field of movement.
				double current_direction = k_directions[direction];
				double angle_delta;
				if (target_direction > current_direction) 
					angle_delta = target_direction - current_direction;
				else
					angle_delta = current_direction - target_direction;

				if (angle_delta > k_pi) 
					angle_delta = k_double_pi - angle_delta;

				if (angle_delta > k_under_half_pi) 
					continue;
			} 

			// Make sure there aren't any adjacent friends.
			for (t_direction dir = t_direction(0); dir < k_direction_count; enum_incr( dir ))
			{
				t_adv_map_point adjacent_point( point + get_direction_offset( dir ) );

				if ( (adjacent_point.row < 0) 
						|| (adjacent_point.row >= m_map.get_size()) 
						|| (adjacent_point.column < m_map.get_row_start( adjacent_point.row )) 
						|| (adjacent_point.column >= m_map.get_row_end( adjacent_point.row )) )
					continue;

				if ( m_map.is_trigger( adjacent_point ) )
				{
					t_adventure_object* adjacent_object = m_map.get_trigger_object( adjacent_point, &army );
					if (adjacent_object && dynamic_cast<t_army*>(adjacent_object) && (adjacent_object->get_owner() == NULL))
						continue;
				}
			}

			if ( (direction != -1) || randomize_direction )
				potential_destinations.push_back(point);
			else
				sorted_destinations[integer_direction].push_back(point);
			
			continue;
		} 

		const std::vector<int>& triggers = tile.get_triggers(point.on_bridge);
		for (std::vector<int>::const_reverse_iterator iter = triggers.rbegin(); iter != triggers.rend(); iter++)
		{
			t_adventure_object* object = &m_map.get_adv_object(*iter);
			assert(object != NULL); 

			t_army* enemy_army = object->get_army();

			if ( (object->get_owner() != NULL) && (enemy_army == NULL) )
			{
				if (army.get_living_hero_count() == 0)
					continue;

				t_creature_array* garrison = object->get_creature_array();
				if ( garrison 
						&& (army.get_living_hero_count() != 0)
						&& !garrison->empty() 
						&& !should_neutral_army_attack( army, *garrison) ) 
					continue;
				
				if (dynamic_cast< t_owned_adv_object* >( object ))
				{
					closest_trigger = path_data.move_cost;
					destination = point;
					targeted_player = object->get_owner();
				} 
				else
					assert(false);

				continue;
			}

			// If a reasonably powered enemy is in view, target it.
			if ( (enemy_army != NULL) 
					&& (enemy_army->get_owner() != NULL) 
					&& should_neutral_army_attack( army, *enemy_army ) 
					&& enemy_army->get_stealth_level() <= army.get_anti_stealth_level()
					&& !enemy_army->is_graveyard()
					&& !enemy_army->is_boat()) 
			{
				destination = point;
				closest_trigger = path_data.move_cost;
				targeted_player = enemy_army->get_owner();
				continue;
			}
		}
	}	

	dominate_direction = 0;
	int dominate_count = 0;
	for ( int i = 1; i < 8; i++ )
	{
		int available_dests = direction_counter[i];
		if (direction_counter[dominate_direction] <= available_dests)
		{
			dominate_count = available_dests;
			dominate_direction = i;
		}
	}

	// Calculate the dominate direction
	std::vector< int > reasonable_directions;
	for ( int i = 0; i < 8; i++ )
	{
		int delta = dominate_count - direction_counter[i];
		if (delta < 0) delta *= -1;
		if (delta < 5) 
			reasonable_directions.push_back(i);
	}

	int choice_count = reasonable_directions.size();
	if (choice_count)
		dominate_direction = reasonable_directions[ choice_count > 1 ? random( 0, choice_count - 1 ) : 0];
	else 
		dominate_direction = 0;

	if (closest_trigger != -1)
	{
		if (targeted_player)
			request_player( m_map, targeted_player );

		t_adventure_path path;
		path_search.get_path( destination, path );
		army.set_path( path );

		return k_wander_target_object;
	} 
	else 
	{
		t_map_point_array& destinations = 
			((direction == -1) && !randomize_direction) ?
				sorted_destinations[dominate_direction]
				:
				potential_destinations;

		int size = destinations.size();
		if (size == 0)
			return k_wander_target_none;
		
		t_adventure_path path;
		if (size == 1)
			path_search.get_path( destinations[0], path );
		else
			path_search.get_path( destinations[random( 0, size - 1 )], path );
			
		army.set_path(path);

		return k_wander_target_tile;
	}
}

void t_adventure_ai::process_guarding_army( t_army& army )
{
	t_adventure_path_finder path_search( m_map );
	t_visited_adv_points	visited_points;
	path_search.set_army( &army );
	path_search.set_path_type ( k_path_search_ai_guarding_army );
	path_search.seed_position( visited_points, army.get_movement() / 2 );

	bool destination_found = false;
	t_player* targeted_player = NULL;
	t_visited_adv_points::iterator index;
	for (index = visited_points.begin(); index != visited_points.end(); ++index)
	{
		t_adv_map_point& point = *index;
		t_adventure_tile& tile = m_map.get_adv_tile(point);

		const std::vector<int>& triggers = tile.get_triggers(point.on_bridge);
		for (std::vector<int>::const_reverse_iterator iter = triggers.rbegin(); iter != triggers.rend(); iter++)
		{
			t_adventure_object* object = &m_map.get_adv_object(*iter);
			assert(object != NULL); 

			if (object->get_owner() == NULL) continue;

			t_army* enemy_army = object->get_army();

			if (enemy_army != NULL)
			{
				if ((enemy_army->is_boat() && enemy_army->empty())
					|| enemy_army->is_graveyard() 
					|| !should_neutral_army_attack( army, *enemy_army ))
					continue;

				if (enemy_army->get_stealth_level() > army.get_anti_stealth_level())
					continue;

				t_adventure_path path;
				bool reached = path_search.get_path( point, path );
				if (reached == false)
				{
					assert(false);
					continue;
				}

				targeted_player = enemy_army->get_owner();
				destination_found = true;
			
				army.set_path( path );
				break;
			}
			else
			{
				if ( army.get_living_hero_count() == 0 )
					continue;

				t_creature_array* garrison = object->get_creature_array();

				if ( (garrison 
						&& (army.get_living_hero_count() != 0)	
						&& !garrison->empty() 
						&& !should_neutral_army_attack( army, *garrison))
						|| path_search.get_existing_data( point ).actual_enemy_adjacent ) 
					continue;
				
				if (dynamic_cast< t_owned_adv_object* >( object ))
				{
					t_adventure_path path;
					bool reached = path_search.get_path( point, path );
					if (reached == false)
					{
						assert(false);
						continue;
					}

					targeted_player = object->get_owner();
					destination_found = true;

					army.set_path( path );
					break;
				} 
				else
				{
					assert(false);
				}
			}
		}
	}
	if (destination_found)
	{
		if (targeted_player)
			request_player( m_map, targeted_player );

		t_counted_ptr<t_army_mover> mover = new t_army_mover(army.get_map_window(), &army);
		while (!mover->is_done())
		{
			process_message();
		}

		path_search.clear();

		if (m_map.is_game_over() || army.is_graveyard() || army.empty()) 
			return;

		t_adventure_path path;
		t_adv_map_point const& initial_point = army.get_initial_location();
		if (path_search.get_path(initial_point, path))
		{
			army.set_path(path);
			t_counted_ptr<t_army_mover> mover = new t_army_mover(army.get_map_window(), &army);
			while (!mover->is_done())
			{
				process_message();
			}
		}

		if ( army.get_position() != initial_point )
			army.move( initial_point );
	}
}

t_adventure_path const&	t_adventure_ai::get_current_path() const
{
	return m_current_path;
}

void t_adventure_ai::set_current_path( t_adventure_path const& path )
{
	m_current_path = path;
}

float t_adventure_ai::get_ship_construction_barrier() const
{
	return m_ship_construction_barrier;
}

t_material_array const&	t_adventure_ai::get_ship_cost() const
{
	return m_boat_cost;
}

void t_adventure_ai::visit_town( t_town& town, t_creature_array& visitor )
{
	if (town.get_ai_town_data_cache()->is_threatened())
	{
		reinforce_army( *this, town.get_garrison(), visitor );

		supplement_army( town, town.get_garrison(), visitor );

		visitor.get_ai_data_cache()->set_sleeping(true);
	}
	else
	{
		reinforce_army( *this, visitor, town.get_garrison() );

		supplement_army( town, visitor, town.get_garrison() );

		if ( visitor.empty() && visitor.get_army() )
			visitor.get_army()->destroy();
	}
}

namespace 
{
	struct t_building_option
	{
		t_town*			town;
		int				town_number;
		t_town_building	building;
		float			value;
	};

	struct t_compare_option_values
	{
		bool operator() (t_building_option const& left, t_building_option const& right)
		{
			return left.value > right.value;
		}
	};

	typedef std::vector<t_building_option> t_sorted_options;
};

void t_adventure_ai::consider_building_options()
{
	t_town_list& towns = *m_current_player->get_towns();
	int town_count = towns.size();
	if (town_count == 0)
		return;
	
	t_town_list::iterator	iter = towns.begin(),
							iter_end = towns.end();

	t_sorted_options options;

	t_material_values const &material_values = m_current_player->get_material_values();

	std::vector<float> town_values( town_count, 0.0f );

	int current_town = -1;
	while (iter != iter_end)
	{
		current_town++;
		t_town_ptr town_ptr = *iter++;

		if (town_ptr->has_built())
			continue;
		
		float cost_values[k_town_building_count];
		float product_values[k_town_building_count];
		std::fill(&cost_values[0], &cost_values[k_town_building_count], 0.0f);
		std::fill(&product_values[0], &product_values[k_town_building_count], 0.0f);
		
		for (t_town_building i = t_town_building(0); i < k_town_building_count; enum_incr(i))
		{
			if (!town_ptr->is_legal(i) && town_ptr->is_enabled(i, true))
				continue;

			t_material_array cost = get_traits( town_ptr->get_type(), i ).cost;
			material_values.adjust_material_values( cost );

			cost_values[i] = cost.get_sum();
			product_values[i] = get_product_value( town_ptr, i );

			if (town_ptr->has(i))
				town_values[current_town] += product_values[i];
		}

		apply_value_of_building_prerequisites( town_ptr, product_values );

		for (t_town_building i = t_town_building(0); i < k_town_building_count; enum_incr(i))
		{
			if (!town_ptr->is_legal(i) || town_ptr->has(i))
				continue;

			t_building_option option;
			option.town = town_ptr;
			option.town_number = current_town;
			option.building = i;
			option.value = product_values[i] / cost_values[i];

			options.push_back( option );
		}
	}

	convert_town_values_to_scaling_factors( town_count, town_values );

	int option_count = options.size();
	if (option_count == 0)
		return;

	t_sorted_options sorted_options;

	for (int i = 0; i < option_count; i++)
	{
		t_building_option& option = options[i];
		option.value *= town_values[option.town_number];
		t_sorted_options::iterator 
			index = std::lower_bound( sorted_options.begin(), sorted_options.end(), option, t_compare_option_values() );
		sorted_options.insert( index, option );
	}
	
	t_material_array discretionary_funds = m_current_player->ai_get_discretionary_funds();

	for (int i = 0; i < option_count; i++)
	{
		t_building_option const& best_option = sorted_options[i];
		t_material_array const& cost = get_traits(best_option.town->get_type(), best_option.building).cost;

		if ((discretionary_funds > cost) 
				&& !best_option.town->has_built() 
				&& best_option.town->can_build(best_option.building) 
				&& best_option.town->is_enabled(best_option.building) )
		{
			best_option.town->buy_building(best_option.building);
			discretionary_funds -= cost;
		}
	}

	m_current_player->ai_set_discretionary_funds( discretionary_funds );
}

void t_adventure_ai::convert_town_values_to_scaling_factors( int count, std::vector<float>& town_values )
{
	// Values will scale between 1.0f and 1.5f
	float low_value = std::numeric_limits< float >::max();
	float high_value = 0.0f;
	for (int i = 0; i < count; i++)
	{
		if (town_values[i] < low_value)
			low_value = town_values[i];
		if (town_values[i] > high_value)
			high_value = town_values[i];
	}

	float value_range = (high_value - low_value) * 2;

	for (int i = 0; i < count; i++)
	{
		if (value_range == 0.0f)
			town_values[i] = 1.0f;
		else
			town_values[i] = 1.0f + ( (town_values[i] - low_value) / value_range );
	}
}

float t_adventure_ai::get_product_value( t_town* town, t_town_building building )
{
	float value = 0.0f;
	switch( building )
	{
		case k_town_hall:
			value += m_current_player->get_material_value(k_gold) * 1750;
			break;
		case k_town_city_hall:
			value += m_current_player->get_material_value(k_gold) * 3500;
		
		case k_town_fort:
		case k_town_citadel:
		case k_town_castle:
			value += town->ai_value( true ) * 0.01f;
			break;
		
		case k_town_dwelling_1:
		case k_town_dwelling_2:
		case k_town_dwelling_3:
		case k_town_dwelling_4:
		case k_town_dwelling_5:
		case k_town_dwelling_6:
		case k_town_dwelling_7:
		case k_town_dwelling_8:
		{
			t_creature_type type = get_traits( town->get_type(), building ).creature;
			int growth = get_traits( type ).weekly_growth;
			
			t_creature creature(type, growth);

			return creature.ai_value();
		}

		case k_town_treasury:
			value += m_current_player->get_material_value(k_gold) 
						* pow( 1.1, ( 1.0 / 7.0 ) ) - 1.0;
			break;
	}
			
	return value;
}

void t_adventure_ai::apply_value_of_building_prerequisites( t_town* town, float* product_values )
{
	float raw_product_values[k_town_building_count];
	for (int j = 0; j < k_town_building_count; j++)
		raw_product_values[j] = product_values[j];

	for (t_town_building i = t_town_building(0); i < k_town_building_count; enum_incr(i))
		ai_distribute_value_to_requirements( town, i, product_values, raw_product_values );
}

bool t_adventure_ai::consider_alternate_destinations(bool clear_path_finder)
{
	if (impending_defeat())
		return false;

	if (clear_path_finder)
		m_path_finder.clear();

	int index = get_map_index(m_map, m_current_army->get_position());
	float value_drop = (*m_danger_map_ptr)[index];
	if (value_drop >= 0.95f)
		return false;

	float value = 0.0f;
	if (choose_alternate_destination( m_alt_dest, value ))
	{
		if (m_current_army_cache->get_target() == m_alt_dest)  
			return false;

		m_has_alt_dest = true;

		return true;
	}

	return false;
}

int t_adventure_ai::calculate_value_of_alt_location( t_adv_map_point const& point, float& location_value )
{
	t_adventure_object* object = m_map.get_trigger_object( point, m_current_army );
	if ((object == NULL) || (object->get_creature_array() != NULL))
		return -1;

	t_adventure_path_data& data = m_path_finder.get_existing_data(point);

	int danger_index, index;
	get_point_indices( point, danger_index, index );

	float value_drop = (*m_danger_map_ptr)[danger_index];
	float total_drop = data.danger_value + value_drop;

	if (total_drop >= 0.95f)
	{
		// If we can move to the square, and still have enough mps to get back to safety, let's do so.
//		if ( (data.danger_value >= 0.95f) 
//			|| ( (m_current_army->get_movement() >> 2) > data.move_cost ) )
			return -1;
	}

	float value_loss = total_drop * m_current_army_value;

	if ((data.value - value_loss) < 0.0f)
		return -1;

	return data.step_count;
}

bool t_adventure_ai::choose_alternate_destination( t_adv_map_point& best_destination, float& actual_value )
{
	t_map_point_array destinations;
	find_potential_destinations( destinations, 
									std::min(m_current_army->get_movement(), 600),
									true );

	if (m_current_army_cache->is_sleeping())
		return false;

	int		best_distance = std::numeric_limits< int >::max();
	int		size = destinations.size();
	int		best_index = -1;

	actual_value = 0.0f;
	
	for (int i = 0; i < size; i++) {
		float location_value;
		int distance = calculate_value_of_alt_location(destinations[i], location_value);

		if (distance == -1)
			continue;

		if ( ( distance < best_distance ) && ( location_value > 0.0f ) ) 
		{
			best_distance = distance;
			actual_value = location_value;
			best_index = i;
		}
	}

	if ( (best_index == -1) || (best_distance > 3) || ( actual_value <= 0.0f ) )
		return false;
	
	best_destination = destinations[best_index];

	return true;
}

int t_adventure_ai::get_hero_count() const
{
	return m_hero_count;
}

void t_adventure_ai::consider_caravans()
{
	if (!m_current_player->can_create_army())
		return;
	
	int iteration = (m_map.get_day() % 5);
	
	if (iteration != 0 )
		return;
	
	m_last_caravan_usage = iteration;

	t_town_list*	towns = m_current_player->get_towns();
	t_town_list		caravan_capable_towns;

	t_town_list::iterator 
		iter = towns->begin(),
		iter_end = towns->end();

	while (iter != iter_end)
	{
		t_town_ptr town_ptr = *iter++;
		if (town_ptr->has( k_town_caravan ))
			caravan_capable_towns.push_back(town_ptr);
	}

	if (caravan_capable_towns.empty())
		return;

	t_adv_dwelling_list const& dwellings = m_current_player->get_dwellings();
	t_adv_dwelling_list::const_iterator 
		dwelling_iter = dwellings.begin(),
		dwelling_end = dwellings.end();

	while (dwelling_iter != dwelling_end)
	{
		t_adv_dwelling_ptr dwelling_ptr = *dwelling_iter++;
		consider_dwelling_caravan( dwelling_ptr, caravan_capable_towns );
	}

	consider_town_caravans( caravan_capable_towns );
}

void t_adventure_ai::consider_town_caravans( t_town_list& caravan_towns )
{
	if (m_last_army == NULL)
		return;

	t_ai_army_data_cache const* cache = m_last_army->get_ai_data_cache();
	t_town* nearest_town = cache->get_nearest_town();

	if (nearest_town == NULL)
		return;

	t_adv_map_point nearest_town_trigger;
	if (!get_adjacent_space( m_map, nearest_town, nearest_town_trigger ))
		return;
	t_adventure_path_finder town_search( m_map );
	int player_number = m_map.get_player_number( m_current_player->get_color() );
	int nearest_town_distance = cache->get_nearest_town_distance();

	t_town_list::iterator
		iter = caravan_towns.begin(),
		iter_end = caravan_towns.end();
				
	t_adventure_path path;
	while (iter != iter_end)
	{
		t_town_ptr town_ptr = *iter++;

		t_adv_map_point trigger_point;
		
		if ( (town_ptr.get() == nearest_town) 
				|| town_ptr->get_ai_town_data_cache()->is_threatened()
				|| town_ptr->empty())
			continue;

		t_pathfinding_subject_ptr subject_ptr =  new t_pathfinding_subject( &m_map, player_number, t_caravan::k_daily_movement );
		if ( !start_object_adjacent_pathfind( town_search, *town_ptr, 
											  *subject_ptr, k_path_search_caravan,
											  bound_handler( *subject_ptr, &t_pathfinding_subject::set_position ) ) )
		{
			continue;
		}

		town_search.get_path( nearest_town_trigger, path );

		if (path.size() == 0) 
			continue;
		
		int path_cost = path[0].move_cost;
		if ( (nearest_town_distance * 1.5f) > path_cost )
			continue;

		t_creature_purchaser purchaser( *town_ptr.get() );
		purchaser.go_shopping(*town_ptr.get(), town_ptr->get_garrison(), NULL);

		int travel_time = ( nearest_town_distance + t_caravan::k_daily_movement - 1 ) / t_caravan::k_daily_movement;

		t_caravan_ptr caravan_ptr = new t_caravan( &m_map, m_map.get_day() + travel_time,
												town_ptr.get(), nearest_town, player_number );
		caravan_ptr->swap( town_ptr->get_garrison() );

		m_map.add_caravan( caravan_ptr );
		m_current_player->add( caravan_ptr );
	}
}

void t_adventure_ai::consider_dwelling_caravan( t_adv_dwelling_ptr dwelling_ptr, t_town_list& caravan_towns )
{
	int							player_number = m_map.get_player_number( m_current_player->get_color() );

	t_adventure_path_finder caravan_search( m_map );
	t_pathfinding_subject_ptr subject_ptr = new t_pathfinding_subject( &m_map, player_number, t_caravan::k_daily_movement );

	if ( !start_object_adjacent_pathfind( caravan_search, *dwelling_ptr, 
										  *subject_ptr, k_path_search_caravan,
										  bound_handler( *subject_ptr, &t_pathfinding_subject::set_position ) ) )
	{
		return;
	}

	t_town_list::iterator 
		iter = caravan_towns.begin(),
		iter_end = caravan_towns.end();

	int best_town_distance = std::numeric_limits< int >::max();
	t_town_ptr best_town_ptr;
	while (iter != iter_end)
	{
		t_town_ptr town_ptr = *iter++;
		t_adv_map_point trigger;
		if (!town_ptr->get_trigger_cell( trigger ))
			continue;
		t_adventure_path_data const& data = caravan_search.get_data( trigger );
		if ( !data.blocked_by_enemy && (best_town_distance > data.move_cost) && data.visited )
		{
			best_town_ptr = town_ptr;
			best_town_distance = data.move_cost;
		}
	}

	if (best_town_ptr.get() == NULL)
		return;

	t_creature_traits const& traits = get_traits( dwelling_ptr->get_creature_type() );
	int dwelling_count = dwelling_ptr->get_population();
	
	t_material_array const& discretionary_funds = m_current_player->ai_get_discretionary_funds();
	int can_afford = discretionary_funds / traits.cost;
	if (can_afford > dwelling_count)
		can_afford = dwelling_count;

	if (can_afford > 0)
	{
		t_material_array actual_cost = traits.cost * can_afford;
		m_current_player->spend( actual_cost );
		m_current_player->ai_set_discretionary_funds( discretionary_funds - actual_cost );
		dwelling_ptr->set_fractional_population( dwelling_ptr->get_fractional_population() - (can_afford * t_adv_dwelling::k_population_divisor));
		
		int travel_time = ( best_town_distance + t_caravan::k_daily_movement - 1 ) / t_caravan::k_daily_movement;

		t_caravan_ptr caravan_ptr = new t_caravan( &m_map, m_map.get_day() + travel_time,
												dwelling_ptr, best_town_ptr, player_number );
		caravan_ptr->add( dwelling_ptr->get_creature_type(), can_afford );

		m_map.add_caravan( caravan_ptr );
		m_current_player->add( caravan_ptr );
	}
}

bool t_adventure_ai::impending_defeat() const
{
	int town_count = m_current_player->get_town_count();
	if (town_count <= 1)
	{
		if (town_count == 0) 
		{
			if (m_map.get_standard_victory_condition())
			{
				return true;
			}
		}
		else
		{
			t_town* town = *m_current_player->get_towns()->begin();
			t_ai_town_data_cache* town_cache = town->get_ai_town_data_cache();
			if (town_cache->is_threatened() && (town_cache->get_value_drop() >= 1.0f))
				return true;
		}
	}

	return (m_map.get_winning_team() != -1);
}

bool t_adventure_ai::ignore_pathing_danger() const
{
	return m_current_army_in_danger;
}

void t_adventure_ai::set_current_army( t_creature_array* army, bool build_danger )
{
	m_current_army = army;
	if (army == NULL)
	{
		m_current_army_cache = NULL;
		m_current_army_value = 0.0f;
		m_current_army_object = 0;
	}
	else
	{ 
		army->get_virtual_position( m_current_army_position );
		m_current_army_index = get_map_index( m_map, m_current_army_position );
		m_current_army_cache = army->get_ai_data_cache();
		m_current_army_value = army->ai_value();
		m_current_army_object = army->get_adventure_object();

		if (build_danger)
		{
			m_path_finder.clear();
			m_path_finder.set_army( army );

			build_danger_map();
		}

		m_current_army_danger = (*m_danger_map_ptr)[m_current_army_index];
		m_current_army_in_danger = m_current_army_danger >= 0.95f;

		if (m_logging)
		{
			m_log_file << format_string("< (%3d,%3d,%3d) - #%d (MPs: %d)>\n", m_current_army_position.row, m_current_army_position.column, m_current_army_position.level, m_move_number, m_current_army->get_movement() );
			m_log_file.flush();
		}

	}
}

bool t_adventure_ai::can_create_army() const
{
	if (!m_current_player->can_create_army())
		return false;

	t_army_array* armies = m_current_player->get_armies();

	if (armies == NULL)
		return true;

	t_army_array::iterator
		iter = armies->begin(),
		iter_end = armies->end();

	int size = 0;

	while (iter != iter_end)
	{
		t_army_ptr army_ptr = *iter++;
		if (army_ptr->get_patrol_type() != k_patrol_guard)
			size++;
	}
		
	switch (m_map.get_map_size_type())
	{
		case k_map_size_small:
			if (size >= 2) 
				return false;
			break;
		case k_map_size_medium:
			if (size >= 3)
				return false;
			break;
		case k_map_size_large:
		case k_map_size_extra_large:
			if (size >= 4)
				return false;
			break;
	}
	return true;
}

t_ai_army_builder::t_ai_army_builder( t_adventure_ai const& ai, t_creature_array const& target, t_creature_array const& source, bool fixed_target )
	:	m_ai(ai), m_fixed_target(fixed_target), 
		m_lesser_army( target.get_map(), target.get_owner() ), 
		m_greater_army( source.get_map(), source.get_owner() ),
		m_both_locked(false)
{
	init( target, source );

	build_initial_armies( target, source );
}

void t_ai_army_builder::build_initial_armies( t_creature_array const& target, t_creature_array const& source)
{
	m_greater_army.clear();
	m_lesser_army.clear();

	bool shuffle_creatures = true;

	if (is_fixed_army( target ))
	{
		shuffle_creatures = false;
		if (m_target_stronger)
			apply_locks( target, m_greater_army_locks );
		else
			apply_locks( target, m_lesser_army_locks );
	}
	if (is_fixed_army( source ))
	{
		if (!shuffle_creatures)
		{
			m_both_locked = true;
			return;
		}

		shuffle_creatures = false;
		if (m_target_stronger)
			apply_locks( source, m_lesser_army_locks );
		else
			apply_locks( source, m_greater_army_locks );
	}

	if (!shuffle_creatures || ((target.get_hero_count() + source.get_hero_count()) > 2) )
	{
		transfer_armies( target, source );
		return;
	}

	add_army( target );
	add_army( source );

	int total_creatures = m_creatures.size();

	t_builder_creature_array::iterator
		iter = m_creatures.begin(),
		end_iter = m_creatures.end();

	int lesser_count = total_creatures - 7;
	int greater_count = 0;
	if (lesser_count > 0)
	{
		greater_count = total_creatures - lesser_count;
		while (lesser_count--)
		{
			assert(iter != end_iter);
			m_lesser_army.swap( *iter, lesser_count );
			iter++;
		}
	}
	else
		greater_count = total_creatures;
	
	while (greater_count--)
	{
		assert(iter != end_iter);
		m_greater_army.swap( *iter, greater_count );
		iter++;
	}
}

void t_ai_army_builder::transfer_armies( t_creature_array const& target, t_creature_array const& source )
{
	for (int i = 0; i < t_creature_array::k_size; i++)
	{
		t_creature_stack_ptr target_clone_ptr;
		if (target[i].get_const_hero() != NULL)
			target_clone_ptr = const_cast<t_hero*>(target[i].get_const_hero());
		else
			target_clone_ptr = target[i].clone();

		t_creature_stack_ptr source_clone_ptr;
		if (source[i].get_const_hero() != NULL)
			source_clone_ptr = const_cast<t_hero*>(source[i].get_const_hero());
		else
			source_clone_ptr = source[i].clone();

		if (m_target_stronger)
		{
			m_greater_army.swap( target_clone_ptr, i );
			m_lesser_army.swap( source_clone_ptr, i );
		}
		else
		{
			m_greater_army.swap( source_clone_ptr, i );
			m_lesser_army.swap( target_clone_ptr, i );
		}
		m_greater_army.consolidate();
		m_lesser_army.consolidate();
	}

}

void t_ai_army_builder::init( t_creature_array const& target, t_creature_array const& source )
{
	if (m_fixed_target)
	{
		m_initial_value = target.ai_value();
		m_target_stronger = true;
	}
	else
	{
		// Store of the pre-shuffle value of the armies.
		float value_of_target = target.ai_value_including_dead();
		float value_of_source = source.ai_value_including_dead();

		if (value_of_target > value_of_source )
		{
			m_target_stronger = true;
			m_initial_value = value_of_target;
		}
		else
		{
			m_target_stronger = false;
			m_initial_value = value_of_source;
		}
	}
}

void t_ai_army_builder::add_army( t_creature_array const& army )
{
	for ( int i = 0; i < t_creature_array::k_size; i++ )
	{
		add_creature( army[i] );
	}
}

void t_ai_army_builder::add_creature( t_creature_stack const& stack )
{
	if (!merge_with_existing_data( stack )) 
	{
		// We didn't find an existing stack to merge with, so make a new entry.
		t_creature_stack_ptr clone_ptr;
		if (stack.get_const_hero() != NULL)
			clone_ptr = const_cast<t_hero*>(stack.get_const_hero());
		else
			clone_ptr = stack.clone();

		t_builder_creature_array::iterator iter = std::lower_bound( m_creatures.begin(), 
																	 m_creatures.end(), clone_ptr,
																	 t_compare_creature_value(m_ai) );
		m_creatures.insert( iter, clone_ptr );
	}
}

bool t_ai_army_builder::merge_with_existing_data( t_creature_stack const& stack )
{
	if (stack.get_creature_type() != k_creature_none)
	{
		t_builder_creature_array::iterator 
			iter = m_creatures.begin(),
			end = m_creatures.end();

		while (iter != end)
		{
			t_creature_stack_ptr creature_ptr = *iter;
			if ( creature_ptr->get_creature_type() == stack.get_creature_type() )
			{
				t_creature* dest_creature = creature_ptr->get_creature();
				t_creature const* src_creature = stack.get_const_creature();
				
				if ((dest_creature == NULL) || (src_creature == NULL))
					break;
				
				dest_creature->add( *src_creature );

				m_creatures.erase( iter );

				iter = std::lower_bound( m_creatures.begin(), m_creatures.end(), creature_ptr,
										  t_compare_creature_value(m_ai) );
				
				m_creatures.insert( iter, creature_ptr );

				return true;
			} 
			iter++;
		}
	}
	else
		if (stack.get_const_hero() == NULL)
			return true;

	return false;
}

float t_ai_army_builder::shuffle_armies()
{
	if (m_both_locked)
		return 0.0f;

	bool swapped = true;
	
	while ( swapped )
	{
		int source, destination;
		if (find_best_swap(source, destination))
		{
			t_creature_stack_ptr swap_ptr( &m_lesser_army[source] );
			m_greater_army.swap( swap_ptr, destination );
			m_lesser_army.swap( swap_ptr, source );
		}
		else
			swapped = false;
	}

	return m_greater_army.ai_value_including_dead() - m_initial_value;
}

bool t_ai_army_builder::find_best_swap(int& source, int& destination)
{
	source = -1;
	destination = -1;
	float best_delta = 0.0f;

	float current_value = m_greater_army.ai_value_including_dead();

	for (int i = 0; i < t_creature_array::k_size; i++)
	{
		if (m_greater_army_locks[i])
			continue;
		for (int j = 0; j < t_creature_array::k_size; j++)
		{
			if (m_lesser_army_locks[i])
				continue;

			int count_before = m_greater_army.get_hero_count();
			t_creature_stack_ptr swap_ptr( &m_lesser_army[j] );
			m_greater_army.swap( swap_ptr, i);
			int count_after = m_greater_army.get_hero_count();

			if ( ((count_before < count_after) && (count_after > 2))
					|| ((count_after == 0) && (count_before != 0)) )
			{
				m_greater_army.swap( swap_ptr, i );
				continue;
			}

			float new_value = m_greater_army.ai_value_including_dead();
			float delta = new_value - current_value;
			if (delta > 0.0f)
			{
				if ((source == -1) || (delta > best_delta))
				{
					source = j;
					destination = i;
					best_delta = delta;
				}
			} 
			else 
			{
				if ((count_before == 0) && (count_after == 1))
				{
					source = j;
					destination = i;
					best_delta = std::numeric_limits< float >::max();
				}
			}
			m_greater_army.swap( swap_ptr, i );
		}
	}

	return (source != -1);
}

void t_ai_army_builder::build_armies( t_creature_array& stronger, t_creature_array& weaker )
{
	if (m_both_locked)
		return;

	stronger.swap_creatures( m_greater_army );
	weaker.swap_creatures( m_lesser_army );

//	swap_artifacts( stronger, weaker );
	
	m_greater_army.clear();
	m_lesser_army.clear();
}

bool t_ai_army_builder::is_target_stronger() const
{
	return m_target_stronger;
}

void t_ai_army_builder::swap_artifacts( t_creature_array& stronger, t_creature_array& weaker )
{
	return;  // Still a problem with artifact swapping...  Have to skip it.

	t_artifact_list artifacts;
	for (int i = 0; i < t_creature_array::k_size; i++)
	{
		build_artifact_list( stronger[i], artifacts );
		build_artifact_list( weaker[i], artifacts );
	} 
	
	t_artifact_list::iterator 
		iter = artifacts.begin(),
		iter_end = artifacts.end();

	while (iter != iter_end)
	{
		t_artifact& artifact = *iter++;
		ai_give_artifact_to_army( stronger, artifact );
	}
}

t_adv_ai_data_cache::t_adv_ai_data_cache()
{
}
	
void t_adv_ai_data_cache::reset_army()
{
	m_alignment_modifier_map.clear();
	m_army_value_map.clear();
	m_stack_value_map.clear();
	m_swap_value_map.clear();
	m_town_value_map.clear();
	m_distance_points_map.clear();
	m_combat_value_map.clear();
	m_combat_value_lost_map.clear();
}

void t_adv_ai_data_cache::reset_player()
{
	m_danger_points_map.clear();
	m_value_points_map.clear();
}

void t_adv_ai_data_cache::reset_danger()
{
	m_danger_points_map.clear();
}

float t_adv_ai_data_cache::get_ai_value( t_creature_stack const* stack )
{
	t_stack_value_map::value_type element( stack, 0.0f );
	std::pair< t_stack_value_map::iterator, bool > insert_results = m_stack_value_map.insert(element);
	if (insert_results.second)
		insert_results.first->second = stack->ai_value();
	return insert_results.first->second;
}

void t_adv_ai_data_cache::build_distance_points( t_adventure_map& map, t_adv_ai_data_cache::t_distance_map_info& info,
												 t_adv_map_point const& location, int move_points, t_creature_array* array )
{
	info.points.clear();
	info.move_points = move_points;
	info.position = location;

	int movement_points = array->get_movement();
	if (movement_points <= 0) return;

	t_visited_adv_points visited;
	t_adventure_path_finder friendly_path_finder(map);
	friendly_path_finder.set_army(array);
	friendly_path_finder.set_path_type( k_path_search_ai_distance );
	friendly_path_finder.seed_position( visited, movement_points );

	info.points.resize( visited.size() );

	int point_index = 0;
	for (t_visited_adv_points::iterator index = visited.begin(); index != visited.end(); ++index )
	{
		t_adv_map_point& point = *index;
		t_adventure_path_data& data = friendly_path_finder.get_existing_data( point );
		t_distance_point& distance_point = info.points[point_index++];
		distance_point.index = get_map_index( map, point );
		distance_point.distance = data.move_cost;
	}
}

t_adv_ai_data_cache::t_distance_points const& t_adv_ai_data_cache::get_distance_points( t_adventure_map* map, t_adv_map_point const& point, 
																	  int move_points, t_creature_array* array )
{
	t_distance_points_map::value_type element( array, t_distance_map_info() );
	std::pair< t_distance_points_map::iterator, bool > insert_results = m_distance_points_map.insert(element);
	t_adv_ai_data_cache::t_distance_map_info& data = insert_results.first->second;
	if (insert_results.second)
	{
		build_distance_points( *map, data, point, move_points, array );
	} 
	else 
	{
		if ((point != data.position) || (move_points != data.move_points))
			build_distance_points( *map, insert_results.first->second, point, move_points, array );
	} 

	return insert_results.first->second.points;
}

t_visited_adv_points const& t_adv_ai_data_cache::get_danger_points( t_adventure_map* map, t_creature_array* array )
{
	
	t_danger_points_map::value_type element( array, t_visited_adv_points() );
	std::pair< t_danger_points_map::iterator, bool > insert_results = m_danger_points_map.insert(element);
	if (insert_results.second)
	{
		t_visited_adv_points& points = insert_results.first->second;
		
		t_adventure_path_finder danger_generator( *map );
		danger_generator.set_army( array );

		if (array->get_patrol_type() == k_patrol_guard)
			danger_generator.set_path_type( k_path_search_ai_guard_danger );
		else
			danger_generator.set_path_type( k_path_search_ai_danger );

		declare_timer( timer, "t_adv_ai_data_cache::get_danger_points() generating points");

		danger_generator.seed_position( points, array->get_max_movement() + k_ai_danger_movement_buffer );
	}
	return insert_results.first->second;
}

t_visited_adv_points const& t_adv_ai_data_cache::get_value_points( t_adventure_map* map, t_adventure_object const* object, t_player* player )
{
	t_value_points_map::value_type element( object, t_visited_adv_points() );
	std::pair< t_value_points_map::iterator, bool > insert_results = m_value_points_map.insert(element);

	t_adventure_path_point prev_point( t_adv_map_point( -1, -1, -1, 0) );
	prev_point.move_cost = 0;
	prev_point.barrier_value = 0.0f;
	prev_point.danger_value = 0.0f;
	prev_point.adjusted_move_cost = 0;
	prev_point.blocked_by_enemy = 0;
	prev_point.step_count = 0;
	prev_point.move_remaining = std::numeric_limits< unsigned int>::max();

	if (insert_results.second)
	{
		t_value_pathfinding_subject subject( map, object, map->get_player_number( player->get_color() ) );
		t_adventure_path_finder	value_generator( *map );

		value_generator.set_army( &subject );
		value_generator.set_path_type( k_path_search_ai_value );

		t_footprint const&				footprint =	object->get_footprint();
		t_map_point_2d					footprint_size = footprint.get_size();

		if ( (footprint_size.row != 1) || (footprint_size.column != 1) )
		{
			t_level_map_point_2d			origin = map->get_object_pos( object->get_map_id() );
			t_adv_map_point					point;
			t_map_point_2d					offset;

			insert_results.first->second.push_back( t_adv_map_point( origin, false ) );

			// look at each point in footprint, looking for trigger cells.
			for (offset.row = 0; offset.row < footprint_size.row; offset.row++)
			{
				for (offset.column = 0; offset.column < footprint_size.column; offset.column++)
				{
					if (!footprint.is_trigger_cell( offset ))
						continue;

					// compute the different ways a size x size square can overlap this trigger
					// move off the trigger in a given direction.
					for (t_direction direction = t_direction(0); direction < k_direction_count; 
						 enum_incr( direction ))
					{
						// find the new point.
						point = t_adv_map_point(origin + offset + get_direction_offset( direction ), false);

						// find out if this region is blocked.
						if (!map->is_valid( point ) || !map->is_open( point, subject ))
							continue;

						// find out if by moving in the opposite direction, we cross
						// the trigger edge.
						if (map->get_trigger_object( point, t_direction( (direction + 4) & 7 ), 0 ) == NULL)
							continue;

						prev_point.pathing_state = map->is_ocean( point ) ? k_army_path_state_ship : k_army_path_state_normal;

						value_generator.push( point, prev_point, 0 );

						insert_results.first->second.push_back( point );
					}
				}
			}
		}
		else
		{
			insert_results.first->second.push_back( object->get_position() );
		}

		value_generator.seed_position( insert_results.first->second, k_ai_value_search_distance );
	}
	return insert_results.first->second;

}

float t_adv_ai_data_cache::get_ai_value( t_creature_array const* army )
{
	t_army_value_map::value_type element( army, 0.0f);
	std::pair<t_army_value_map::iterator, bool> insert_results = m_army_value_map.insert(element);
	if (insert_results.second)
		insert_results.first->second = army->ai_value();
	return insert_results.first->second;
}

float t_adv_ai_data_cache::get_ai_value( t_town const* town )
{
	t_town_value_map::value_type element( town, 0.0f);
	std::pair<t_town_value_map::iterator, bool> insert_results = m_town_value_map.insert(element);
	if (insert_results.second)
		insert_results.first->second = town->ai_value();
	return insert_results.first->second;
}

void t_adv_ai_data_cache::reset_ai_value( t_creature_stack const* stack )
{
	m_stack_value_map.erase( stack );
}

void t_adv_ai_data_cache::reset_ai_value( t_creature_array const* army )
{
	m_army_value_map.erase( army );
}

void t_adv_ai_data_cache::reset_ai_value( t_town const* town )
{
	m_town_value_map.erase( town );
}

float t_adv_ai_data_cache::value_of_creature_swap( t_adventure_ai const& ai, t_creature_array const& target, t_creature_array const& source )
{
	t_creature_array_pair pair( &target, &source );
	t_creature_pair_map::value_type element(pair, 0.0f);
	std::pair<t_creature_pair_map::iterator, bool> insert_results = m_swap_value_map.insert(element);
	if (insert_results.second)
	{
		t_ai_army_builder builder( ai, target, source );
		insert_results.first->second = builder.shuffle_armies();
	}
	return insert_results.first->second;
}

float t_adv_ai_data_cache::value_of_combat( t_creature_array const& attacker, t_creature_array const& defender )
{
	t_creature_array_pair pair( &attacker, &defender );
	t_creature_pair_map::value_type element(pair, 0.0f);
	std::pair<t_creature_pair_map::iterator, bool> insert_results = m_combat_value_map.insert(element);
	if (insert_results.second)
	{
		insert_results.first->second = ::value_of_combat( &attacker, &defender );
	}
	return insert_results.first->second;
}

float t_adv_ai_data_cache::value_lost_in_combat( t_creature_array const& attacker, t_creature_array const& defender, bool attacker_location )
{
	t_creature_array_pair pair( &attacker, &defender );
	t_creature_pair_map::value_type element(pair, 0.0f);
	std::pair<t_creature_pair_map::iterator, bool> insert_results = m_combat_value_lost_map.insert(element);
	if (insert_results.second)
	{
		insert_results.first->second = ::value_lost_in_combat( &attacker, &defender, attacker_location );
	}
	return insert_results.first->second;
}

t_adv_ai_data_cache::t_alignment_array const& t_adv_ai_data_cache::get_alignment_modifiers( t_creature_array const* army )
{
	t_alignment_array modifiers;
	t_alignment_modifier_map::value_type element( army, modifiers );
	std::pair<t_alignment_modifier_map::iterator, bool> insert_results = m_alignment_modifier_map.insert(element);
	if (insert_results.second) 
	{
		static int modifiers[] = { 0, -1, -2, -5 };

		std::bitset<k_town_type_count> has_alignment;
		bool has_undead = false;
		for (int i = 0 ; i < t_creature_array::k_size; i++ )
		{
			t_creature_stack const& stack = (*army)[i];
			if (stack.get_number() == 0)
				continue;
			has_alignment.set( stack.get_alignment() );
			if (stack.is_undead())
				has_undead = true;
		}
		for (t_town_type j = t_town_type(0); j < k_town_type_count; enum_incr( j ))
			if (has_alignment[j]) 
			{
				int result = 1;
				for (t_town_type k = t_town_type(0); k < k_town_type_count; enum_incr( k ))
				{
					if (has_alignment[k])
						result += modifiers[get_alignment_relationship( j, k )];
				}
				if (has_undead && j != k_town_death)
					result -= 2;

				insert_results.first->second[j] = result;
			}
	}
	return insert_results.first->second;
}

int t_adv_ai_data_cache::get_alignment_modifier( t_creature_array const* array, t_town_type alignment )
{
	t_alignment_array const& values = get_alignment_modifiers( array );
	return values[alignment];
}

void get_town_production_options( t_town const* town, t_production_options& options, bool owned_dwellings = true, bool buy_buildings = false )
{
	for (t_town_building i = k_town_dwelling_1; i <= k_town_dwelling_8; enum_incr(i))
	{
		bool has_building = town->has(i);
		bool can_buy_building = buy_buildings 
									&& !has_building 
									&& town->can_build(i) 
									&& town->is_enabled(i);
		if (can_buy_building || (owned_dwellings && has_building) )
		{
			t_building_traits const& traits = get_traits( town->get_type(), i );
			t_creature_type type = traits.creature;
			t_creature_traits const& creature_traits = get_traits( type );
			t_material_array const& cost = creature_traits.cost;
			int dwelling = i - k_town_dwelling_1;

			int population = 0;
			if (!has_building)
				population = (creature_traits.weekly_growth + 1) / 2;
			else
			{
				population = town->get_population(dwelling);
				if (population == 0)
					continue;
			}

			t_production_options::iterator 
				iter = std::find_if( options.begin(), options.end(), t_find_production_type( type ) );
			if (iter == options.end()) 
			{
				t_production_option desc;
				desc.type = type;
				desc.hero = NULL;
				desc.count = population;
				desc.per_value = creature_traits.experience;
				desc.total_value = desc.count * desc.per_value;
				desc.cost = cost;
				if (can_buy_building)
					desc.building_cost = &traits.cost;
				else
					desc.building_cost = 0;
				desc.building_type = i;
				options.push_back(desc);
			}
			else
			{
				t_production_option& desc = *iter;
				desc.count += population;
				desc.total_value += population * desc.per_value;
			}
		}
	}
}

void get_production_options( t_player* player, t_production_options& options, int count )
{
	t_town_list*			towns = player->get_towns();
	t_town_list::iterator	town_iter = towns->begin(),
							town_iter_end = towns->end();

	while (town_iter != town_iter_end)
	{
		t_town_ptr town_ptr = *town_iter++;		
		get_town_production_options( town_ptr, options );
	}

	if (!options.empty() && count)
	{
		std::sort( options.begin(), options.end(), t_production_value_order() );
		int i = 0;
		t_production_options::iterator iter = options.begin(),
									end = options.end();
		while (iter != end)
		{
			if (++i > count)
			{
				options.erase( iter, options.end());
				return;
			}
			iter++;
		}
	}
}

bool shuffle_armies( t_adventure_ai const& ai, t_creature_array& target, t_creature_array& source, bool& target_stronger, bool cleanup_empty )
{
	t_ai_army_builder builder( ai, target, source );
	float shuffle_value = builder.shuffle_armies();
	if (shuffle_value > 0.0f)
	{
		if (builder.is_target_stronger())
		{
			builder.build_armies( target, source );
			builder.swap_artifacts( target, source );
			if ( cleanup_empty && source.empty() && source.get_army() )
				source.get_army()->destroy();
			target_stronger = true;
			return true;
		}
		else
		{
			builder.build_armies( source, target );
			builder.swap_artifacts( source, target );
			if ( cleanup_empty && target.empty() && target.get_army() )
				target.get_army()->destroy();
			target_stronger = false;
			return true;
		}
	}
	return false;
}

void reinforce_army( t_adventure_ai const& ai, t_creature_array& target, t_creature_array& source )
{
	t_ai_army_builder builder( ai, target, source, true );
	float shuffle_value = builder.shuffle_armies();
	if (shuffle_value > 0.0f)
	{
		builder.build_armies( target, source );
		builder.swap_artifacts( target, source );
		if (source.empty() && source.get_army() && !source.is_boat())
			source.get_army()->destroy();
	}
}

t_creature_purchaser::t_creature_purchaser( t_town const& town, t_creature_array const& army, 
											t_creature_array const* orphan_army, bool purchase_building, bool include_heroes ) 
 : m_original_army( &army ), m_original_orphan( orphan_army ), m_purchased_hero(NULL), m_include_heroes( include_heroes ),
	m_purchased_building_type( k_town_building_none ),
	m_using_discretionary_funds( false )
{
	m_purchased_building = (!purchase_building) || town.has_built();
	m_map = town.get_map();
	m_owner = town.get_owner();
	m_funds = m_owner->get_funds();
	m_army = ai_deep_copy_of_creature_array_minus_hero( army );
	if (orphan_army)
		m_orphan_army = ai_deep_copy_of_creature_array_minus_hero( *orphan_army );
	calculate_town_purchase_options( town );
}

t_creature_purchaser::t_creature_purchaser( t_town const& town ) 
 : m_original_orphan( NULL ), m_purchased_hero(NULL), m_include_heroes( false ),
	m_purchased_building_type( k_town_building_none ), m_purchased_building( true ),
	m_using_discretionary_funds( true )
{
	m_original_army = &town.get_garrison();
	m_map = town.get_map();
	m_owner = town.get_owner();
	m_funds = m_owner->ai_get_discretionary_funds();
	m_army = ai_deep_copy_of_creature_array_minus_hero( *m_original_army );
	calculate_town_purchase_options( town );
}

t_creature_purchaser::t_creature_purchaser( t_adv_dwelling const& dwelling, t_creature_array const& army )
 : m_original_army( &army ), m_original_orphan( NULL ), 
	m_purchased_hero(NULL), m_purchased_building_type( k_town_building_none ),
	m_using_discretionary_funds( false )
{
	m_purchased_building = true;
	m_map = dwelling.get_map();
	m_owner = dwelling.get_owner();
	m_funds = m_owner->get_funds();
	m_army = ai_deep_copy_of_creature_array_minus_hero( army );

	calculate_dwelling_purchase_options( dwelling );
}

t_creature_purchaser::~t_creature_purchaser()
{
	if (m_map != NULL)
	{
		t_adventure_map* map = const_cast<t_adventure_map*>(m_map); // I hate to do this, but anything else
																	// is way too non-trivial at this point.
		
		int size = m_included_default_heroes.size();
		for (int i = 0; i < size; i++)
		{
			t_default_hero const& default_hero = m_included_default_heroes[i];
			map->free_hero_usage( default_hero.biography_id, default_hero.portrait_id );
		}
	}
}

t_material_array const& t_creature_purchaser::get_cost() const
{
	return m_cost;
}

void t_creature_purchaser::calculate_town_purchase_options( t_town const& town )
{
	m_options.clear();
	get_town_production_options( &town, m_options, true, !m_purchased_building);

	if (m_include_heroes)
		calculate_tavern_options( town );
}

void t_creature_purchaser::calculate_dwelling_purchase_options( t_adv_dwelling const& dwelling )
{
	t_creature_traits const& traits = get_traits( dwelling.get_creature_type() );

	m_options.clear();

	t_production_option option;
	option.type = dwelling.get_creature_type();
	option.building_cost = NULL;
	option.building_type = k_town_building_none;
	option.per_value = t_creature( option.type, 1 ).ai_value();
	option.count = dwelling.get_population();
	option.cost = traits.cost;
	option.hero = NULL;
	option.total_value = option.per_value * option.count;
	m_options.push_back(option);
}

void t_creature_purchaser::calculate_tavern_options( t_town const& town )
{
	bool has_tavern = town.has( k_town_tavern );

	if (!has_tavern)
	{
		if ( m_purchased_building
			|| (town.get_tavern_delay() != 0)
			|| !town.can_buy( k_town_tavern )
			|| !town.is_enabled( k_town_tavern ))
			return;
	}				

	if (m_army->get_hero_count() != 0)
		return;

	// This is temporary
	int limit = ((town.get_map()->get_day() + 1) / 7) + 2;
	if (limit > 4) limit = 4;
	int count = town.get_ai()->get_hero_count();
	if (count >= limit)
		return;

	if ( (town.get_tavern_delay() == 0)
			&& (m_army->can_add_hero() || 
				((m_orphan_army.get() != NULL) && m_orphan_army->can_add_hero()) ) )
	{
		// Only consider buying a single hero.
		for (int i = 0; i < t_creature_array::k_size; i++)
			if ((*m_army)[i].get_const_hero() != NULL)
				return;
		
		t_material_array const* tavern_cost; 
		if ( has_tavern )
		{
			tavern_cost = NULL;
		}
		else
			tavern_cost = &get_traits( town.get_type(), k_town_tavern ).cost;

		int hire_costs[k_hero_class_basic_count];
		get_hero_hiring_cost( town.get_type(), hire_costs );

		for ( t_hero_class hero_class = t_hero_class(0); hero_class < k_hero_class_basic_count; enum_incr(hero_class))
		{
			int& cost = hire_costs[hero_class];
			if ((cost == 0) || (m_funds[k_gold] < cost))
				continue;

			std::vector<t_default_hero>	
				heroes = 
					(random(0, 1) == 0) ?
						m_map->get_unused_heroes( hero_class, true )
						:
						m_map->get_unused_heroes( hero_class, false );

			int selected_hero = random(0, heroes.size() - 1);
			t_default_hero const& used_hero = heroes[selected_hero];
			t_counted_ptr<t_hero> hero = m_map->create_hero( used_hero, get_alignment( hero_class ) );

			t_production_option option;
			option.type = k_creature_none;
			option.hero = hero;
			option.count = 1;
			option.per_value = option.total_value = hero->ai_value() + k_ai_value_bonus_for_buying_hero;
			option.cost[k_gold] = cost;
			option.building_cost = tavern_cost;
			option.building_type = k_town_tavern;
			m_included_heroes.push_back( hero );
			m_included_default_heroes.push_back( used_hero );
			m_options.push_back(option);
		}
	} 
}

void t_creature_purchaser::go_shopping( t_town& town, t_creature_array& original_army, t_creature_array* orphan_army, bool freebies )
{
	float value = 0.0f;	
	do {
		value = do_best_purchase();
	} while (value > 0.0f);
	original_army.swap_creatures( *m_army );
	if (orphan_army != NULL)
		orphan_army->swap_creatures( *m_orphan_army );

	if (!freebies)
		apply_charges( town );

	save_cost();
}

void t_creature_purchaser::save_cost()
{
	if (m_using_discretionary_funds)
		m_cost = m_owner->ai_get_discretionary_funds() - m_funds;
	else
		m_cost = m_owner->get_funds() - m_funds;
}

void t_creature_purchaser::apply_charges( t_town& town )
{
	t_adventure_map* map = town.get_map();
	if (m_purchased_hero != NULL)
	{
		town.set_tavern_delay( k_town_tavern_delay );
		map->record_hero_usage( m_purchased_hero->get_biography_id(), m_purchased_hero->get_portrait_id() );
	}

	if (m_purchased_building_type != k_town_building_none)
	{
		town.create_building( m_purchased_building_type );
		town.apply_building_delay();
	}

	if (m_using_discretionary_funds)
	{
		m_owner->ai_spend_discretionary( m_cost );
	}
	else
	{
		m_owner->spend( m_cost );
	}
	
	t_creatures_spent::iterator 
		iter = m_creatures_spent.begin(),
		end_iter = m_creatures_spent.end();

	while (iter != end_iter)
	{
		town.adjust_population( get_traits( iter->first ).dwelling - k_town_dwelling_1, -iter->second );
		*iter++;
	}
}

void t_creature_purchaser::go_shopping( t_adv_dwelling& dwelling, t_creature_array& army )
{
	float value = 0.0f;	
	do {
		value = do_best_purchase();
	} while (value > 0.0f);

	army.swap_creatures( *m_army );

	m_owner->set_funds( m_funds );

	t_creatures_spent::iterator 
		iter = m_creatures_spent.begin(),
		end_iter = m_creatures_spent.end();

	while (iter != end_iter)
	{
		dwelling.set_fractional_population( dwelling.get_fractional_population() - (iter->second * t_adv_dwelling::k_population_divisor));
		*iter++;
	}
	
	save_cost();
}


float t_creature_purchaser::query_shopping_value()
{
	float value = 0.0f;	
	do {
		float ret_value = do_best_purchase();
		if (ret_value > 0.0f)
			value += ret_value;
		else 
			break;
	} while (true);

	return value;
}

float t_creature_purchaser::do_best_purchase()
{
	t_production_options::iterator	iter = m_options.begin(),
									end = m_options.end(),
									best_iter;
	float							best_value = 0.0f;
	int								best_index = -1;
	int								best_amount = 0;
	float							best_value_increase = 0.0f;
	int								day = m_map->get_day();
	
	while (iter != end)
	{
		t_production_option& option = *iter;

		// Skip heroes if we've already purchased one.
		if ((m_purchased_hero != NULL) && (option.hero != NULL))
		{
			iter++;
			continue;
		}
		
		t_material_array total_cost = option.cost * option.count;

		if (option.building_cost && m_purchased_building)
		{
			iter++;
			continue;
		}
		
		int can_afford;
		if (option.building_cost)
		{
			if (m_funds > *option.building_cost)
				can_afford = (m_funds - *option.building_cost) / option.cost;
			else
				can_afford = 0;
		}
		else
			can_afford = m_funds / option.cost;

		if (can_afford > option.count)
			can_afford = option.count;

		if (can_afford > 0)
		{
			t_material_array actual_cost = option.cost * can_afford;
			if (option.building_cost)
				actual_cost += *option.building_cost;
			float value_divisor = m_owner->get_material_values().adjust_material_values(actual_cost).get_sum();
			t_creature_stack_ptr new_stack_ptr;
			
			if (option.type == k_creature_none)
				new_stack_ptr = option.hero;
			else
			{
				new_stack_ptr = new t_creature( option.type, can_afford );
				new_stack_ptr->process_new_day( NULL, false, NULL, day );
			}

			float	value_before = m_army->ai_value();
			bool	compared_empty_creature = false;

			for (int i = 0; i < t_creature_array::k_size; i++)
			{
				t_creature_stack& original = (*m_army)[i];
				bool no_creature = (( original.get_creature_type() == k_creature_none ) && (original.get_const_hero() == NULL));
				bool same_creature = original.can_add( option.type );

				if (no_creature || ( !same_creature 
										&& (m_orphan_army.get() != NULL) 
										&& m_orphan_army->can_add( original.get_creature_type() ) ) ) 
				{
					if (no_creature)
					{
						if (compared_empty_creature)
							continue;
						compared_empty_creature = true;
					}
					m_army->swap( new_stack_ptr, i );
					float value_diff = (m_army->ai_value() - value_before);
					float compare_value = value_diff / value_divisor;
					if ((best_index == -1) || (compare_value > best_value))
					{
						best_index = i;
						best_iter = iter;
						best_value = compare_value;
						best_value_increase = value_diff;
						best_amount = can_afford;
					}
					m_army->swap( new_stack_ptr, i );
				} 
				else 
					if (same_creature)
					{
						t_creature_stack_ptr clone_ptr;
						if (original.get_const_hero() != NULL)
							clone_ptr = t_creature_stack_ptr(&original);
						else
						{
							clone_ptr = original.clone();
							t_creature* cloned_creature = clone_ptr->get_creature();
							assert( cloned_creature );
							cloned_creature->add( *new_stack_ptr->get_creature() );
						}
						m_army->swap( clone_ptr, i );
						float value_diff = (m_army->ai_value() - value_before);
						float compare_value = value_diff / value_divisor;
						if ((best_index == -1) || (compare_value > best_value))
						{
							best_index = i;
							best_iter = iter;
							best_value = compare_value;
							best_value_increase = value_diff;
							best_amount = can_afford;
						}
						m_army->swap( clone_ptr, i );
					}
			}
		} 
		iter++;
	}

	if ((best_index != -1) && (best_value_increase > 0.0f))
		execute_best_purchase( best_iter, best_index, best_amount, day );
	else
		best_value_increase = 0.0f;

	return best_value_increase;
}

void t_creature_purchaser::execute_best_purchase(t_production_options::iterator best_iter, int best_index, int best_amount, int day)
{
	if (best_index != -1)
	{
		t_production_option& option = *best_iter;

		if (option.building_cost) 
		{
			m_purchased_building = true;
			m_funds -= *option.building_cost;
			m_purchased_building_type = option.building_type;
		}

		m_funds -= option.cost * best_amount;

		t_creature_stack_ptr stack_ptr;
		
		if (option.type != k_creature_none )
		{
			stack_ptr = new t_creature( option.type, best_amount );
			stack_ptr->process_new_day( NULL, false, NULL, day );
			t_creature_stack& source_stack = (*m_army)[best_index];
			t_creature* source_creature = source_stack.get_creature();
			if ( source_stack.can_add( option.type ) && (source_creature != NULL) )
			{
				source_creature->add( *(stack_ptr->get_creature()) );
			}
			else 
			{
				m_army->swap( stack_ptr, best_index );
				if (m_orphan_army.get() != NULL)
					m_orphan_army->add( stack_ptr );
			}
			option.count -= best_amount;
			m_creatures_spent[ option.type ] += best_amount;
		}
		else
		{
			stack_ptr = (m_purchased_hero = option.hero);
			stack_ptr->process_new_day( NULL, false, NULL, day );
			m_army->swap( stack_ptr, best_index );
			if (m_orphan_army.get() != NULL)
				m_orphan_army->add( stack_ptr );
		}

		if (option.count == 0)
			m_options.erase( best_iter );
		else
			option.total_value = option.per_value * option.count;
	}
}

float value_of_reinforcement( t_town const* town, t_creature_array const& target, t_creature_array const& source ) 
{
	t_ai_army target_copy(town->get_map(), town->get_owner());
	t_ai_army source_copy(town->get_map(), town->get_owner());
	target_copy.copy_extra_properties( target );
	source_copy.copy_extra_properties( source );

	assert(town != NULL);
	t_ai_army_builder merger( town->get_map()->get_ai(), target, source, true );
	float value_of_shuffle = merger.shuffle_armies();
	merger.build_armies( target_copy, source_copy );

	t_creature_purchaser purchaser( *town, target_copy, &source_copy, true );

	float value_of_shopping = purchaser.query_shopping_value();

	return value_of_shuffle + value_of_shopping;
}

void supplement_army( t_town& town, t_creature_array& target, t_creature_array& orphans )
{
	t_creature_purchaser purchaser( town, target, &orphans, true );
	purchaser.go_shopping( town, target, &orphans );
}

float value_of_combat(t_creature_array const* attacker, t_creature_array const* defender)
{
	// Simulated combat is currently setup to take non-const pointers to the following
	// data, even though it doesn't modify the data when used this way.  Since it is non-trivial
	// to fix this we've settled with the const_cast solution for now.

	t_creature_array* casted_attacker = const_cast< t_creature_array* >(attacker);
	t_creature_array* casted_defender = const_cast< t_creature_array* >(defender);
	t_simulated_combat simulation( *casted_attacker, casted_attacker->get_owner(), 
									*casted_defender, casted_defender->get_owner(),
									*casted_attacker->get_map(), casted_defender->get_position(), NULL );

	set_ai_effectiveness( simulation, casted_attacker, casted_defender );

	simulation.run(); 

	return simulation.query_combat_value();
}

float value_lost_in_combat(t_creature_array const* attacker, t_creature_array const* defender, bool attacker_location)
{
	// Simulated combat is currently setup to take non-const pointers to the following
	// data, even though it doesn't modify the data when used this way.  Since it is non-trivial
	// to fix this we've settled with the const_cast solution for now.

	t_creature_array* casted_attacker = const_cast< t_creature_array* >(attacker);
	t_creature_array* casted_defender = const_cast< t_creature_array* >(defender);
	t_simulated_combat simulation( *casted_attacker, casted_attacker->get_owner(), 
									*casted_defender, casted_defender->get_owner(),
									*casted_attacker->get_map(), attacker_location ? casted_attacker->get_position() : casted_defender->get_position(), NULL );

	set_ai_effectiveness( simulation, casted_attacker, casted_defender );

	simulation.run(); 

	return simulation.query_value_drop();
}

bool survives_combat_series( t_creature_array* attacker, t_creature_list * defenders, float& value_loss )
{
	t_creature_list::iterator	iter = defenders->begin(),
									end = defenders->end();
	
	t_owned_ptr<t_creature_array> attacking_force = ai_deep_copy_of_creature_array( *attacker );
	
	float previous_value = attacking_force->ai_value();

	while (iter != end) 
	{
		t_creature_array* defender = *iter++;

		t_simulated_combat simulation( *attacking_force, attacking_force->get_owner(), 
										*defender, defender->get_owner(),
										*attacker->get_map(), defender->get_position(), NULL
										);

		simulation.run(); 

		simulation.update_attacking_force();

		if (!attacking_force->is_alive())
		{
			// We've lost our entire army.
			value_loss = 1.0f;
			return false;
		}
	}

	float value_after = attacking_force->ai_value();

	if (value_after == 0.0f)
	{
		value_loss = 1.0f;
		return false;
	}
	else
		value_loss = 1.0f - (value_after / previous_value);
	
	return true;
}

std::auto_ptr< t_creature_array > ai_copy_of_creature_array( t_creature_array const& army )
{
	std::auto_ptr< t_creature_array > result( new t_ai_army( army.get_map(), army.get_owner() ) );

	result->set_ai_data_cache( army.get_ai_data_cache() );
	result->set_patrol_type( army.get_patrol_type() );
	result->set_patrol_radius( army.get_patrol_radius() );
	result->set_initial_location( army.get_initial_location() );
	
	// Close your eyes here!  The much dreaded const_cast...  There was
	// no other easy solution considering we're staring with a const 
	// t_creature_array.
	for (int i = 0; i < t_creature_array::k_size; i++)
		result->add( const_cast<t_creature_stack *>( &army[i] ), i );
	
	return result;
}

std::auto_ptr< t_creature_array > ai_deep_copy_of_creature_array( t_creature_array const& army )
{
	std::auto_ptr< t_creature_array > result( new t_ai_army( army.get_map(), army.get_owner() ) );

	t_creature_array::t_ai_data_cache_ptr new_cache_ptr = new t_ai_army_data_cache;
	*new_cache_ptr = *army.get_ai_data_cache();

	result->set_ai_data_cache( new_cache_ptr );
	result->set_patrol_type( army.get_patrol_type() );
	result->set_patrol_radius( army.get_patrol_radius() );
	result->set_initial_location( army.get_initial_location() );
	
	for (int i = 0; i < t_creature_array::k_size; i++)
		result->add( army[i].clone(), i );
	
	return result;
}

std::auto_ptr< t_creature_array > ai_deep_copy_of_creature_array_minus_hero( t_creature_array const& army )
{
	std::auto_ptr< t_creature_array > result( new t_ai_army( army.get_map(), army.get_owner() ) );

	t_creature_array::t_ai_data_cache_ptr new_cache_ptr = new t_ai_army_data_cache;
	*new_cache_ptr = *army.get_ai_data_cache();

	result->set_ai_data_cache( new_cache_ptr );
	result->set_patrol_type( army.get_patrol_type() );
	result->set_patrol_radius( army.get_patrol_radius() );
	result->set_initial_location( army.get_initial_location() );
	
	for (int i = 0; i < t_creature_array::k_size; i++)
	{
		t_hero const* hero = army[i].get_const_hero();
		if (hero != NULL)
			result->add( const_cast<t_hero*>(hero), i );
		else 
			result->add( army[i].clone(), i );
	}
	
	return result;
}

